fork download
copy 
  1. #include <cassert>
  2. #include <ctime>
  3. #include <cstdio>
  4. #include <cstring>
  5. #include <vector>
  6.  
  7. const int maxn = 10010;
  8.  
  9. using std::vector;
  10.  
  11. vector <int> g[maxn];
  12. int n1, n2, m, test = 0;
  13. int c[maxn], r[maxn], l1[maxn], l2[maxn], ok[maxn], step = 100;
  14. int q[maxn], qs, qz;
  15.  
  16. bool dfs( int u )
  17. {
  18.   c[u] = step;
  19.   for (int i = 0; i < (int)g[u].size(); i++)
  20.   {
  21.     int to = g[u][i];
  22.     if (l2[to] != l1[u] + 1)
  23.       continue;
  24.     if (r[to] == -1 || (c[r[to]] != step && dfs(r[to]) && l1[r[to]] == l1[u] + 2))
  25.     {
  26.       r[to] = u;
  27.       return true;
  28.     }
  29.   }
  30.   return false;
  31. }
  32.  
  33. bool dfs2( int u )
  34. {
  35.   c[u] = step;
  36.   for (int i = 0; i < (int)g[u].size(); i++)
  37.   {
  38.     int to = g[u][i];
  39.     if (r[to] != -1 && c[r[to]] != step)
  40.       dfs2(r[to]);
  41.   }
  42.   return false;
  43. }
  44.  
  45. void bfs()
  46. {
  47.   qs = qz = 0;
  48.   memset(c, 0, sizeof(c[0]) * n1);
  49.   memset(l1, -1, sizeof(l1[0]) * n1);
  50.   memset(l2, -1, sizeof(l2[0]) * n2);
  51.   for (int i = 0; i < n1; i++)
  52.     if (!ok[i])
  53.       q[qs + qz++] = i, l1[i] = 1, c[i] = 1;
  54.   while (qz > 0)
  55.   {
  56.     int u = q[qs++]; qz--;
  57.     for (int i = 0; i < (int)g[u].size(); i++)
  58.       if (l2[g[u][i]] == -1)
  59.       {
  60.         l2[g[u][i]] = l1[u] + 1;
  61.         if (r[g[u][i]] != -1 && c[r[g[u][i]]] == 0)
  62.         {
  63.           c[r[g[u][i]]] = 1;
  64.           l1[r[g[u][i]]] = l1[u] + 2;
  65.           q[qs + qz++] = r[g[u][i]];
  66.         }
  67.       }
  68.   }
  69. }
  70.  
  71. int main()
  72. {
  73.   assert(freopen("sociology.in", "r", stdin));
  74.   assert(freopen("sociology.out", "w", stdout));
  75.  
  76.   memset(c, 0, sizeof(c));
  77.   while (scanf("%d%d", &n2, &n1) == 2)
  78.   {
  79.     ++test;
  80.     assert(scanf("%d", &m) == 1);
  81.     for (int i = 0; i < m; i++)
  82.     {
  83.       int a, b;
  84.       assert(scanf("%d%d", &a, &b) == 2);
  85.       g[b - 1].push_back(a - 1);
  86.     }
  87.     memset(r, -1, sizeof(r[0]) * n2);
  88.     memset(ok, 0, sizeof(ok[0]) * n1);
  89.     bool good = true, ans = true;
  90.     while (good)
  91.     {
  92.       good = false;
  93.       bfs();
  94. //      memset(c, 0, sizeof(c[0]) * n1);
  95.       step++;
  96.       for (int i = 0; i < n1; i++)
  97.         if (l1[i] == 1 && c[i] != step && dfs(i))
  98.           ok[i] = true, good = true;
  99.     }
  100.     for (int i = 0; i < n1; i++)
  101.       if (!ok[i])
  102.       {
  103.         ans = false;
  104.         step++;
  105.         dfs2(i);
  106.         break;
  107.       }
  108.     if (ans)
  109.       printf("Case #%d: There is no excessive subset of managers.\n", test);
  110.     else
  111.     {
  112.       vector <int> res;
  113.       for (int i = 0; i < n1; i++)
  114.         if (c[i] == step)
  115.           res.push_back(i + 1);
  116.       if (res.size() == 1)
  117.         printf("Case #%d: Manager %d forms an excessive subset.\n", test, res[0]);
  118.       else
  119.       {
  120.         printf("Case #%d: Managers ", test);
  121.         for (int i = 0; i < (int)res.size(); i++)
  122.         {
  123.           if (i == (int)res.size() - 1)
  124.             printf(" and ");
  125.           else if (i > 0)
  126.             printf(", ");
  127.           printf("%d", res[i]);
  128.         }
  129.         printf(" form an excessive subset.\n");
  130.       }
  131.     }
  132.     for (int i = 0; i < n1; i++)
  133.       g[i].clear();
  134.   }
  135.   fprintf(stderr, "Total time: %.2f\n", (double)clock() / CLOCKS_PER_SEC);
  136.   return 0;
  137. }
  138.  
  139.  
Runtime error #stdin #stdout #stderr 0s 3584KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
prog: prog.cpp:73: int main(): Assertion `freopen("sociology.in", "r", stdin)' failed.
https://ideone.com/th4QEr
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!