fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define fo(i, a, b) for (int i = (a); i <= (b); ++i)
  5. #define fd(i, a, b) for (int i = (a); i >= (b); --i)
  6. #define ii pair<int, int>
  7. #define fi first
  8. #define se second
  9. #define pb push_back
  10. #define all(x) x.begin(), x.end()
  11. const int N = 1e5+5;
  12.  
  13. struct Edge {
  14.     int u, v, c, id;
  15.     Edge(){}
  16.     Edge(int u_, int v_, int c_) {
  17.         u = u_, v = v_, c = c_;
  18.     }
  19.     bool operator < (const Edge &o) const {
  20.         return c < o.c;
  21.     }
  22. };
  23.  
  24. int n, m, fa[N], h[N], up[N][17], mx[N][17], ans[N];
  25. Edge e[N];
  26. vector<ii> g[N];
  27. vector<int> del[N];
  28. bool inMst[N];
  29. multiset<int> s[N];
  30. set<ii> valid;
  31.  
  32. int find(int u) { return fa[u] == u ? u : fa[u] = find(fa[u]); }
  33. bool merge(int u, int v) {
  34.     u = find(u), v = find(v);
  35.     if (u == v) return 0;
  36.     fa[u] = v; return 1;
  37. }
  38.  
  39. void dfs(int u, int pre = -1) {
  40.     for (ii p : g[u]) if (p.fi != pre) {
  41.         int v = p.fi, c = p.se;
  42.         h[v] = h[u] + 1; up[v][0] = u, mx[v][0] = c;
  43.         fo(i, 1, 16) {
  44.             up[v][i] = up[up[v][i-1]][i-1];
  45.             mx[v][i] = max(mx[v][i-1], mx[up[v][i-1]][i-1]);
  46.         }
  47.         dfs(v, u);
  48.     }
  49. }
  50.  
  51. ii get(int u, int v) {
  52.     int mm = 0;
  53.     if (h[u] != h[v]) {
  54.         if (h[u] < h[v]) swap(u, v);
  55.         int d = h[u] - h[v];
  56.         fo(i, 0, 16) if (d>>i&1) {
  57.             mm = max(mm, mx[u][i]);
  58.             u = up[u][i];
  59.         }
  60.     }
  61.     if (u == v) return {v, mm};
  62.     fd(i, 16, 0) if (up[u][i] != up[v][i]) {
  63.         mm = max({mm, mx[u][i], mx[v][i]});
  64.         u = up[u][i], v = up[v][i];
  65.     }
  66.     return {up[u][0], max({mm, mx[u][0], mx[v][0]})};
  67. }
  68.  
  69. void dfs1(int u, int pre = -1) {
  70.     for (ii p : g[u]) if (p.fi != pre) {
  71.         int v = p.fi, c = p.se; dfs1(v, u);
  72.         if (s[v].empty() || c < (*s[v].begin())) {
  73.             valid.insert({u, v});
  74.             valid.insert({v, u});
  75.         }
  76.         if (s[u].size() < s[v].size()) swap(s[u], s[v]);
  77.         s[u].insert(all(s[v]));
  78.     }
  79.     for (int x : del[u]) s[u].erase(s[u].find(x));
  80. }
  81.  
  82. int32_t main() {
  83.     cin.tie(0)->sync_with_stdio(0);
  84.     if (fopen("A.inp", "r")) {
  85.         freopen("A.inp", "r", stdin);
  86. //        freopen("A.out", "w", stdout);
  87.     }
  88.     cin >> n >> m;
  89.     fo(i, 1, n) fa[i] = i;
  90.     fo(i, 1, m) cin >> e[i].u >> e[i].v >> e[i].c, e[i].id = i;
  91.     sort(e+1, e+m+1);
  92.     fo(i, 1, m) if (merge(e[i].v, e[i].u)) {
  93.         g[e[i].v].pb({e[i].u, e[i].c});
  94.         g[e[i].u].pb({e[i].v, e[i].c});
  95.         inMst[e[i].id] = ans[e[i].id] = 1;
  96.     }
  97.     dfs(1);
  98.     // 0 : none, 1 : at least one
  99.     fo(i, 1, m) {
  100.         int u = e[i].u, v = e[i].v, c = e[i].c;
  101.         if (get(u, v).se < c) ans[e[i].id] = 0;
  102.         else if (!inMst[e[i].id]) {
  103.             ans[e[i].id] = 1;
  104.             int lca = get(u, v).fi;
  105.             if (u != lca) {
  106.                 s[u].insert(c);
  107.                 del[lca].pb(c);
  108.             }
  109.             if (v != lca) {
  110.                 s[v].insert(c);
  111.                 del[lca].pb(c);
  112.             }
  113.         }
  114.     }
  115.     dfs1(1);
  116.     fo(i, 1, m) {
  117.         int u = e[i].u, v = e[i].v, c = e[i].c;
  118.         if (valid.count(ii(u, v)))
  119.             ans[e[i].id] = 2;
  120.     }
  121.     fo(i, 1, m) {
  122.         if (ans[i] == 0) cout << "none\n";
  123.         else if (ans[i] == 1) cout << "at least one\n";
  124.         else cout << "any\n";
  125.     }
  126. }
  127.  
Success #stdin #stdout 0.01s 13720KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rLYJhI
language:
C++ (gcc 8.3)
created:
14 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!