fork download
copy 
  1. #include <iostream>
  2. #include <set>
  3. #include <algorithm>
  4. #include <cstdio>
  5. #include <cstring>
  6. #include <stack>
  7. #include <vector>
  8. #include <queue>
  9.  
  10. using namespace std;
  11.  
  12. #define INF 999999
  13. #define pb push_back
  14. #define mp make_pair
  15.  
  16. typedef pair<int, int> pi;
  17.  
  18.  
  19.  
  20.  
  21. const int MAXV = 50005, MAXE = 10500000, oo = (1 << 25);
  22. int E, last[MAXV], nextssss[MAXE], adj[MAXE], level[MAXV], now[MAXV], Q[MAXV], source, sink;
  23. int cap[MAXE], flow[MAXE];
  24.  
  25.  
  26. void add_edge (int u, int v, int c)
  27. {
  28.  
  29.     cap[E] = c, flow[E] = 0, adj[E] = v, nextssss[E] = last[u], last[u] = E++;
  30.     cap[E] =0, flow[E] = 0, adj[E] = u, nextssss[E] = last[v], last[v] = E++;
  31. }
  32.  
  33. #define RES(e)  (cap[e] - flow[e])
  34.  
  35. bool bfs (int s, int t)
  36. {
  37.     memset(level, -1, sizeof level);
  38.     level[s] = 0;
  39.     Q[0] = s;
  40.  
  41.     for (int ql = 0, qr = 1; ql < qr && level[t] == - 1; ++ql)
  42.     {
  43.         int u = Q[ql];
  44.  
  45.         for (int e = last[u]; e != -1; e = nextssss[e])
  46.         {
  47.             int v = adj[e];
  48.  
  49.             if (level[v] == -1 && RES(e) > 0)
  50.             {
  51.                 level[v] = level[u] + 1;
  52.                 Q[qr++] = v;
  53.             }
  54.         }
  55.     }
  56.  
  57.     return level[t] != -1;
  58. }
  59.  
  60. int dfs (int u, int curr)
  61. {
  62.     if (u == sink)
  63.         return curr;
  64.  
  65.     for (int e = now[u]; e != -1; now[u] = e = nextssss[e])
  66.     {
  67.         int v = adj[e];
  68.  
  69.         if (level[v] == level[u] + 1 && RES(e) > 0)
  70.         {
  71.             int ans = dfs(v, min(curr, RES(e)));
  72.  
  73.             if (ans > 0)
  74.             {
  75.                 flow[e] += ans;
  76.                 flow[e ^ 1] -= ans;
  77.                 return ans;
  78.             }
  79.         }
  80.     }
  81.  
  82.     return 0;
  83. }
  84.  
  85. int max_flow ()
  86. {
  87.     int ans = 0, res;
  88.  
  89.     while (bfs(source, sink))
  90.     {
  91.         memcpy(now, last, sizeof now);
  92.  
  93.         while ((res = dfs(source, oo)) > 0)
  94.             ans += res;
  95.     }
  96.  
  97.     return ans;
  98. }
  99.  
  100. int T;
  101. int A[5000], B[5000];
  102. int na, nb;
  103. int m;
  104.  
  105. int flow_a(){
  106.  
  107.     source = 1999;
  108.     sink = 2000;
  109.  
  110.  
  111.     E = 0;
  112.     memset(last, -1, sizeof last);
  113.  
  114.     for(int i = 0 ; i < m; i++){
  115.         add_edge(601+i, sink, 1);
  116.     //    add_edge(sink, 601+i, 1);
  117.     }
  118.  
  119.     for(int i = na - 1, j = 0; i >= 0; i--, j++){
  120.  
  121.         if(j < m){
  122.             add_edge(source, 1 + i, 1);
  123.          //   add_edge(1+i, source, 1);
  124.         }
  125.  
  126.         for(int k = 0; k < nb; k++){
  127.             int diff = abs(A[i] - B[k]);
  128.  
  129.             if(diff < T){
  130.                 add_edge(1+i, 601 + k, 1);
  131.                 add_edge(601+k, 1+i, 1);
  132.             }
  133.         }
  134.  
  135.     }
  136.  
  137.     return max_flow();
  138. }
  139.  
  140. int flow_b(){
  141.  
  142.     source = 0;
  143.     sink = 2000;
  144.  
  145.     E = 0;
  146.     memset(last, -1, sizeof last);
  147.  
  148.     for(int i = 0 ; i < m; i++){
  149.         add_edge(601+i, sink, 1);
  150.       //  add_edge(sink, 601+i, 1);
  151.     }
  152.  
  153.     for(int i = nb - 1, j = 0; i >= 0; i--, j++){
  154.  
  155.         if(j < m){
  156.             add_edge(source, 1 + i, 1);
  157.         //    add_edge(1+i, source, 1);
  158.         }
  159.  
  160.         for(int k = 0; k < na; k++){
  161.             int diff = abs(B[i] - A[k]);
  162.  
  163.             if(diff < T){
  164.                 add_edge(1+i, 601 + k, 1);
  165.                 add_edge(601+k, 1+i, 1);
  166.             }
  167.         }
  168.  
  169.     }
  170.  
  171.     return max_flow();
  172. }
  173.  
  174.  
  175. int main()
  176. {
  177.  
  178.     scanf("%d %d %d %d", &m, &na, &nb, &T);
  179.  
  180.     for(int i = 0 ; i < na; i++)
  181.         scanf("%d", &A[i]);
  182.  
  183.     for(int i = 0; i < nb; i++)
  184.         scanf("%d", &B[i]);
  185.  
  186.     sort(A, A+na);
  187.     sort(B, B+nb);
  188.  
  189.     if( flow_a() == m || flow_b() == m)
  190.         printf("S\n");
  191.     else
  192.         printf("N\n");
  193.  
  194.     return 0;
  195. }
Success #stdin #stdout 0s 168320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
S
https://ideone.com/6sC2ek
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!