YEZAELP

CUBE-190: Supernova

Jan 23rd, 2021 (edited)
108
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.71 KB | None
  1. #include <bits/stdc++.h>;
  2.  
  3. using namespace std;
  4. using pi = pair <int, int>;
  5. using lli = long long;
  6. int n, m;
  7. vector <pi> g[100010];
  8. pi path[100010];
  9. int color[100010], parent[100010];
  10. bool Cycle[100010];
  11. bool cycle;
  12.  
  13. void CYCLE(int u, int pre){
  14.     if(color[u] == 2) return;
  15.     if(color[u] == 1){
  16.         cycle = true;
  17.         int cur = pre;
  18.         Cycle[u] = true;
  19.         while(cur != u){
  20.             Cycle[cur] = true;
  21.             cur = parent[cur];
  22.         }
  23.         return ;
  24.     }
  25.     parent[u] = pre;
  26.     color[u] = 1;
  27.     for(auto v: g[u]){
  28.         if(v.first != pre) {
  29.             CYCLE(v.first, u);
  30.         }
  31.     }
  32.     color[u] = 2;
  33. }
  34.  
  35. int node[100010];
  36. lli ans[100010];
  37.  
  38. int NODE(int u, int pre, int i){
  39.     if(Cycle[u] and i != 0) return 0;
  40.     node[u] = 1;
  41.     for(auto v: g[u]){
  42.         if(v.first != pre) node[u] += NODE(v.first, u, v.second);
  43.     }
  44.     ans[i] = (lli) (n - node[u]) * node[u];
  45.     return node[u];
  46. }
  47.  
  48. int main(){
  49.  
  50.     scanf("%d%d", &n, &m);
  51.  
  52.     for(int i=1;i<=n;i++){
  53.         int u, v;
  54.         scanf("%d%d", &u, &v);
  55.         path[i] = {u, v};
  56.         g[u].push_back({v, i});
  57.         g[v].push_back({u, i});
  58.     }
  59.  
  60.     for(int i=1;i<=n;i++){
  61.         CYCLE(i, 0);
  62.         if(cycle) break;
  63.     }
  64.  
  65.  
  66.     for(int i=1;i<=n;i++){
  67.         if(Cycle[i]) NODE(i, 0, 0);
  68.     }
  69.  
  70.     for(int i=1;i<=n;i++){
  71.         if(Cycle[path[i].first] and Cycle[path[i].second]) printf("0");
  72.         else printf("%lld", ans[i]);
  73.         printf(" ");
  74.     }
  75.  
  76.     return 0;
  77. }
  78. /*
  79. 6 6
  80. 1 2
  81. 2 3
  82. 2 4
  83. 3 4
  84. 4 5
  85. 5 6
  86.  
  87. 11 11
  88. 1 2
  89. 1 3
  90. 1 5
  91. 3 4
  92. 4 5
  93. 3 6
  94. 6 10
  95. 3 7
  96. 7 9
  97. 7 8
  98. 7 11
  99.  
  100. 10 10
  101. 4 3
  102. 8 1
  103. 6 8
  104. 8 5
  105. 7 9
  106. 5 3
  107. 4 9
  108. 2 5
  109. 2 10
  110. 3 10
  111.  
  112. 21 9 9 21 9 0 16 0 0 0
  113.  
  114. */
  115.  
RAW Paste Data Copied