fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define y1 hld
  4. #define int long long
  5. #define pii pair<int, int>
  6. #define vi vector<int>
  7. #define vii vector<pii>
  8. #define fi first
  9. #define se second
  10. #define big (int)1e18
  11. #define small (int)1e9
  12. #define mouse (int)-1e18
  13. #define cat (int)-1e9
  14. #define pb push_back
  15. #define eb emplace_back
  16. struct tri {
  17.     int u, v, w, i;
  18. };
  19. #define all(x) x.begin(), x.end()
  20. #define rall(x) x.rbegin(), x.rend()
  21. #define srt(x) sort(all(x));
  22. #define bit(x, i) ((x >> i) & 1)
  23. #define mask(i) (1LL << i)
  24. #define saiz(x) (int)x.size()
  25. #define uni(x) sort(all(x)), x.erase(unique(all(x)), x.end())
  26. #define debug(x) cerr << x << ' '
  27. #define debg(x) cerr << x << '\n'
  28. #define deb(x, y) cerr << x << ' ' << y << '\n'
  29. #define de(x, y, z) cerr << x << ' ' << y << ' ' << z << '\n'
  30. #define htbd(x, y, z, t) cerr << x << ' ' << y << ' ' << z << ' ' << t << '\n'
  31. template <class T>
  32. using minheap = priority_queue<T, vector<T>, greater<T>>;
  33. int dx[4] = {1, -1, 0, 0};
  34. int dy[4] = {0, 0, 1, -1};
  35. int ceil_div(int a, int b) { return (a + b - 1) / b; }
  36. #define fill0(x) memset(x, 0, sizeof x)
  37. #define f36(x) memset(x, -1, sizeof x)
  38. #define inf(x) memset(x, 0x3f, sizeof x)
  39. #define nyc(x) memset(x, -0x3f, sizeof x)
  40. #define loop(i, a, b) for (int i = (a); i <= (b); i++)
  41. #define back(i, a, b) for (int i = (a); i >= (b); i--)
  42. #define popcnt(x) __builtin_popcountll(x)
  43. #define lb lower_bound
  44. #define ub upper_bound
  45. #define f59(a, b) a = min(a, b)
  46. #define f69(a, b) a = max(a, b)
  47. #define rep(i, n) for (int i = 1; i <= n; i++)
  48. #define has(x, y) (x.find(y) != x.end())
  49. #define each(x, a) for (auto &x : a)
  50. #define lbit(x) (x & -x)
  51. #define f(u, v) adj[u].push_back(v)
  52. #define g(u, v, w) adj[u].push_back({v, w})
  53. #define f2(u, v) (f(u, v), f(v, u))
  54. #define g2(u, v, w) (g(u, v, w), g(v, u, w))
  55. const int N = 2e5 + 5, M = 4e5 + 5;
  56. int n, m;
  57. tri e[M];
  58. int sz[N], p[N], vs[N];
  59. void init() {
  60.     for (int i = 1; i <= n; i++) sz[i] = 1, p[i] = i;
  61. }
  62. int par(int i) {
  63.     if (i == p[i]) return i;
  64.     return par(p[i]);
  65. }
  66. #define uni unI
  67. void uni(int u, int v) {
  68.     u = par(u);
  69.     v = par(v);
  70.     if (u == v) return;
  71.     if (sz[u] > sz[v]) swap(u, v);
  72.     p[u] = v;
  73.     sz[v] += sz[u];
  74. }
  75. int id[N], low[N], b[N];
  76. vector<pii> adj[N];
  77. int timer;
  78. void dfs(int u, int d) {
  79.     id[u] = low[u] = ++timer;
  80.     for (pii v : adj[u]) {
  81.         if (v.se == d) continue;
  82.         if (id[v.fi] == 0)
  83.             low[u] = min(low[u], id[v.fi]);
  84.         else {
  85.             dfs(v.fi, v.se);
  86.             low[u] = min(low[u], low[v.fi]);
  87.             if (low[v.fi] >= id[v.fi]) b[v.se] = 2;
  88.         }
  89.     }
  90. }
  91. signed main() {
  92.     ios_base::sync_with_stdio(0);
  93.     cin.tie(0);
  94.     cout.tie(0);
  95.     cin >> n >> m;
  96.     for (int i = 1; i <= m; i++) cin >> e[i].u >> e[i].v >> e[i].w, e[i].i = i;
  97.     sort(e + 1, e + m + 1, [&](tri a, tri b) { return a.w < b.w; });
  98.     for (int i = 1; i <= m; i++) b[i] = 1;
  99.     init();
  100.     for (int l = 1; l <= m; l++) {
  101.         int r = l;
  102.         while (r < m && e[r + 1].w == e[l].w) r++;
  103.         set<int> nd;
  104.         loop(i, l, r) nd.insert(par(e[i].u)), nd.insert(par(e[i].v)),
  105.             g2(par(e[i].u), par(e[i].v), e[i].i);
  106.         loop(i, l, r) if (par(e[i].u) != par(e[i].v)) b[e[i].i] = 0;
  107.         loop(i, l, r) uni(e[i].u, e[i].v);
  108.         for (int i : nd) dfs(i, -1);
  109.         for (int i : nd) id[i] = low[i] = 0;
  110.         timer = 0;
  111.         for (int i : nd) adj[i].clear();
  112.     }
  113.     loop(i, 1, m) cout << b[i];
  114. }
Success #stdin #stdout 0.01s 10160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/VAg1tQ
language:
C++14 (gcc 8.3)
created:
6 hours 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!