fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5. #define co_tat_ca_nhung_thieu_em using namespace std;
  6. #define ngay_xua_em_che_toi_code_ga ios_base::sync_with_stdio(0);
  7. #define bay_gio_toi_da_ga_hon cin.tie(0);
  8. #define em_da_thay_hoi_han_chua cout.tie(0);
  9. #define __QuocSensei__ int main()
  10. #define ii pair<int, int>
  11. #define fi first
  12. #define se second
  13.  
  14. co_tat_ca_nhung_thieu_em;
  15.  
  16. const int maxn = 1e5;
  17. const int maxw = 1e6;
  18.  
  19. struct edge
  20. {
  21.     int x, y, id;
  22. };
  23.  
  24. int n, m, leader[maxn + 10], sz[maxn + 10], ans[maxn + 10];
  25. int id[maxn + 10], low[maxn + 10], cnt = 0;
  26. vector<edge> v[maxw + 10];
  27. vector<ii> adj[maxn + 10];
  28.  
  29. int find_leader(int x)
  30. {
  31.     if (x == leader[x]) return x;
  32.     return leader[x] = find_leader(leader[x]);
  33. }
  34. void connect(int x, int y)
  35. {
  36.     x = find_leader(x);
  37.     y = find_leader(y);
  38.  
  39.     if (x == y) return ;
  40.     if (sz[x] < sz[y]) swap(x, y);
  41.     sz[x] += sz[y];
  42.     leader[y] = x;
  43. }
  44. void dfs(int top, int par = -1)
  45. {
  46.     id[top] = low[top] = ++cnt;
  47.  
  48.     for (ii p : adj[top])
  49.     {
  50.         int next_top = p.fi;
  51.         int idx = p.se;
  52.         if (idx == par) continue;
  53.         if (id[next_top]) low[top] = min(low[top], id[next_top]);
  54.         else
  55.         {
  56.             dfs(next_top, idx);
  57.             low[top] = min(low[top], low[next_top]);
  58.         }
  59.         if (low[next_top] > id[top]) ans[idx] = 1;
  60.     }
  61. }
  62.  
  63. __QuocSensei__
  64. {
  65.     ngay_xua_em_che_toi_code_ga
  66.     bay_gio_toi_da_ga_hon
  67.     em_da_thay_hoi_han_chua
  68.  
  69.     if (fopen("EDGES_IN_MST.INP", "r"))
  70.     {
  71.         freopen("EDGES_IN_MST.INP", "r", stdin);
  72.         freopen("EDGES_IN_MST.OUT", "w", stdout);
  73.     }
  74.  
  75.     cin >> n >> m;
  76.     for (int i = 1; i <= n; i++)
  77.     {
  78.         leader[i] = i;
  79.         sz[i] = 1;
  80.     }
  81.     for (int i = 1; i <= m; i++)
  82.     {
  83.         int x, y;
  84.         ll w;
  85.         cin >> x >> y >> w;
  86.         v[w].push_back({x, y, i});
  87.     }
  88.     for (int i = 1; i <= 1e6; i++)
  89.     {
  90.         for (edge e : v[i])
  91.         {
  92.             int x = e.x;
  93.             int y = e.y;
  94.             int id = e.id;
  95.  
  96.             if (find_leader(x) == find_leader(y)) ans[id] = 2;
  97.             else
  98.             {
  99.                 adj[find_leader(x)].push_back({find_leader(y), id});
  100.                 adj[find_leader(y)].push_back({find_leader(x), id});
  101.             }
  102.         }
  103.         for (edge e : v[i]) connect(e.x, e.y);
  104.     }
  105.     for (int i = 1; i <= n; i++)
  106.         if (!id[i]) dfs(i);
  107.  
  108.     for (int i = 1; i <= m; i++)
  109.         if (ans[i] == 2) cout << "none", el;
  110.         else if (ans[i] == 1) cout << "any", el;
  111.         else cout << "at least one", el;
  112. }
Success #stdin #stdout 0.01s 29568KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/c32iIJ
language:
C++14 (gcc 8.3)
created:
3 days 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!