fork download
copy 
  1. /***********Template Starts Here***********/
  2. #include <bits/stdc++.h>
  3.  
  4. #define pb push_back
  5. #define ff first
  6. #define ss second
  7. #define MP make_pair
  8. #define FOR(i,x,y) for(vlong i = (x) ; i <= (y) ; ++i)
  9. #define ROF(i,x,y) for(vlong i = (y) ; i >= (x) ; --i)
  10. #define CLR(x,y) memset(x,y,sizeof(x))
  11. #define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())
  12. #define MIN(a,b) ((a)<(b)?(a):(b))
  13. #define MAX(a,b) ((a)>(b)?(a):(b))
  14. #define ALL(x) (x).begin(),(x).end()
  15. #define SZ(x) ((vlong)(x).size())
  16.  
  17. using namespace std;
  18.  
  19. typedef long long vlong;
  20. typedef vector<int> vi;
  21.  
  22. const vlong inf = 2147383647;
  23.  
  24. /***********Template Ends Here***********/
  25.  
  26. struct node {
  27.     int x, y, next, cap, cost;
  28. };
  29.  
  30. #define NODE 20010
  31. #define EDGE 5000010
  32.  
  33. ///Flow Template
  34. struct FLOW {
  35.     int source, sink;
  36.  
  37.     int head[NODE];
  38.     void clear() {
  39.         e = 0;
  40.         CLR(head,-1);
  41.     }
  42.  
  43.     node edge[EDGE]; int e;
  44.     void addEdge ( int u, int v, int cap ) {
  45.         edge[e].x = u; edge[e].y = v; edge[e].cap = cap;
  46.         edge[e].next = head[u]; head[u] = e; e++;
  47.         edge[e].x = v; edge[e].y = u; edge[e].cap = 0;
  48.         edge[e].next = head[v]; head[v] = e; e++;
  49.     }
  50.  
  51.     int vis[NODE], q[NODE], now[NODE];
  52.     bool bfs ( ) {
  53.         memset ( vis, -1, sizeof vis );
  54.         vis[source] = 0;
  55.         int ini = 0, qend = 0;
  56.         q[qend++] = source;
  57.  
  58.         while ( ini < qend && vis[sink] == -1 ) {
  59.             int s = q[ini++];
  60.             int i;
  61.             for (i=head[s];i!=-1;i= edge[i].next){
  62.                 int t = edge[i].y;
  63.                 if ( vis[t] == -1 && edge[i].cap){
  64.                     vis[t] = vis[s] + 1;
  65.                     q[qend++] = t;
  66.                 }
  67.             }
  68.         }
  69.         if ( vis[sink] != -1 ) return true;
  70.         else return false;
  71.     }
  72.     int dfs ( int s, int f ) {
  73.         if ( f == 0 ) return 0;
  74.         if ( s == sink ) return f;
  75.         for ( int &i=now[s];i!=-1;i=edge[i].next){
  76.             int t = edge[i].y;
  77.             if ( vis[s] + 1 != vis[t] ) continue;
  78.             int pushed=dfs(t,MIN(f,edge[i].cap));
  79.             if ( pushed ) {
  80.                 edge[i].cap -= pushed;
  81.                 edge[i^1].cap += pushed;
  82.                 return pushed;
  83.             }
  84.         }
  85.         return 0;
  86.     }
  87.  
  88.     int maxFlow ( int limit, int flow ) {
  89.         int res = 0;
  90.         while ( 1 ) {
  91.             if ( flow == 0 ) break;
  92.             if ( bfs () == false ) break;
  93.             int i;
  94.             for ( i=0;i<=limit;i++)now[i]= head[i];
  95.             while (int pushed=dfs(source,flow ) ) {
  96.                 res += pushed; ///Can overflow depending on Max Flow
  97.                 flow -= pushed;
  98.             }
  99.         }
  100.         return res;
  101.     }
  102. }graph;
  103.  
  104. int vis[10010], vv = 1;
  105. int qqq[10010]; ///Queue for BFS
  106. int total = 0;
  107.  
  108. ///Generate all children
  109. void bfs ( int s, int lim ) {
  110.     int qh, qt;
  111.     qh = qt = 0;
  112.     qqq[qt++] = s;
  113.  
  114.     vis[s] = vv;
  115.  
  116.     while ( qh < qt ) {
  117.         s = qqq[qh++];
  118.  
  119.         FOR(i,0,15) {
  120.             if ( s & ( 1 << i ) ) {
  121.                 int t = s + ( 1 << i ); ///Generate Child
  122.                 if ( t <= lim ) {
  123.                     if ( vis[t] != vv ) { ///Has not been generated before
  124.                         vis[t] = vv;
  125.                         qqq[qt++] = t;
  126.                     }
  127.                 }
  128.             }
  129.         }
  130.     }
  131. }
  132.  
  133. int mp[10010];
  134.  
  135. int main () {
  136.     #ifdef forthright48
  137.     freopen ( "input.txt", "r", stdin );
  138.     //freopen ( "output.txt", "w", stdout );
  139.     #endif // forthright48
  140.  
  141.     int kase;
  142.     scanf ( "%d", &kase );
  143.  
  144.     int cnt = 0;
  145.  
  146.     while ( kase-- ) {
  147.         int n;
  148.         scanf ( "%d", &n );
  149.  
  150.         int l;
  151.         scanf ( "%d", &l );
  152.  
  153.         graph.clear(); ///Clear Graph
  154.  
  155.         vv++; ///Clear visit array
  156.         FOR(i,0,n-1) {
  157.             int seed;
  158.             scanf ( "%d", &seed );
  159.             bfs ( seed, l ); ///Generate all children of seed
  160.         }
  161.  
  162.         vi child;
  163.         FOR(i,1,l) {
  164.             if ( vis[i] == vv ) child.pb ( i ); ///Collect all child in one place
  165.         }
  166.  
  167.         int cur = 1;
  168.         ///Map all children to new nodes. This is necessary to lower node number in Flow
  169.         FOR(i,0,SZ(child)-1) {
  170.             mp[child[i]] = cur++;
  171.         }
  172.  
  173.         int node = child.size();
  174.         graph.source = 0;
  175.         graph.sink = node + node + 1; ///Assign source and sink
  176.  
  177.         FOR(i,1,node) {
  178.             graph.addEdge(0,i,1); ///Add edge from source to left side
  179.             graph.addEdge(i+node,node + node + 1,1); ///Add edge from right side to sink
  180.         }
  181.  
  182.         FOR(c,0,SZ(child)-1) {
  183.             int s = child[c];
  184.             FOR(i,0,15) {
  185.                 if ( s & ( 1 << i ) ) {
  186.                     int t = s + ( 1 << i );
  187.                     if ( t <= l ) {
  188.                         graph.addEdge ( c+1, node + mp[t], 1 ); ///Add edge between left and right side
  189.                     }
  190.                 }
  191.             }
  192.         }
  193.  
  194.         int m = graph.maxFlow(node+node+1,inf); ///Find flow
  195.  
  196.         printf ( "Case %d: %d\n", ++cnt, SZ(child) - m ); ///Result is total - flow
  197.     }
  198.  
  199.     return 0;
  200. }
  201.  
Runtime error #stdin #stdout 0s 101504KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/U1VPNB
Blog
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!