fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int MAXN = 1e5 + 7;
  5. ll par[MAXN], mx[MAXN], q;
  6. set <ll> tplt[MAXN];
  7. bool mark[MAXN];
  8. pair <ll, ll> edge[MAXN];
  9. ll n, m;
  10. ll find(ll u){return par[u] < 0 ? u : par[u] = find(par[u]);}
  11.  
  12. bool join(ll x, ll y){
  13.     x = find(x);
  14.     y = find(y);
  15.     if(x == y) return false;
  16.     if(par[x] > par[y]) swap(x, y);
  17.     mx[x] = max(mx[x], mx[y]);
  18.     tplt[x].insert(mx[x]);
  19.     par[x] += par[y];
  20.     par[y] = x;
  21. }
  22.  
  23. struct DS{
  24.     ll q, u, idx;
  25. };
  26. vector <DS> ds;
  27.  
  28. int main(){
  29.     ios_base::sync_with_stdio(0);
  30.     cout.tie(0);
  31.     cin.tie(0);
  32.     cin >> n >> m >> q;
  33.     for(int i = 1; i <= n; i++) cin >> mx[i];
  34.     fill(par + 1, par + 1 + n, -1);
  35.     for(int i = 1; i <= m; i++){
  36.         ll x, y;
  37.         cin >> x >> y;
  38.         edge[i] = {x, y};
  39.     }
  40.     for(int i = 1; i <= q;i++){
  41.         ll type, u;
  42.         cin >> type >> u;
  43.         ds.push_back({type, u, i});
  44.     }
  45.     for(int i = 1; i <= m; i++){
  46.         ll x = edge[i].first;
  47.         ll y = edge[i].second;
  48.         if(!mark[i]) join(x, y);
  49.     }
  50.     sort(ds.begin(), ds.end(), [&] (DS a, DS b){
  51.         return a.idx > b.idx;
  52.     });
  53.     for(auto [type, u, id] : ds){
  54.         if(type == 1){
  55.             cout << *(--tplt[find(u)].end()) << endl;
  56.             tplt[find(u)].erase(--tplt[find(u)].end());
  57.         }
  58.  
  59.         else {ll x = edge[u].first , y = edge[u].second;
  60.             join(x, y);}
  61.     }
  62.  
  63. }
Success #stdin #stdout 0.01s 9592KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/NiJV3C
language:
C++14 (gcc 8.3)
created:
4 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!