제출 #934044

#제출 시각아이디문제언어결과실행 시간메모리
934044Lemser다리 (APIO19_bridges)C++14
0 / 100
76 ms12804 KiB
#include <bits/stdc++.h> #define endl '\n' #define mp make_pair #define f first #define s second #define pb push_back #define all(x) x.begin(),x.end() #define fore(i,l,r) for(int i = l; i < r;i++) #define forex(i,r,l) for(int i = r; i>= l;i--) #define fo(i,n) fore(i,0,n) #define ffo(i,n) forex(i,n-1,0) #define lsb(x) x&(-x) using namespace std; using ii = pair<int,int>;using ll = long long; using ull = unsigned long long; using vi = vector<int>; const int N = 1e5+7; int res[N]; vector<ii> graph[N]; struct evento{ int peso, a,b,i; }; vector<evento> eventos; bool ord(evento a, evento b){ if(a.peso == b.peso)return a.b > b.b; // las updates primero return a.peso < b.peso; } struct dsu{ vi pa,nh; int gru; dsu(int n){ pa.resize(n+1); nh.resize(n+1); gru = n; fo(i,n+1){ pa[i] = i;nh[i] = 1; } } int find(int i ){ if(pa[i] == i) return i; return pa[i] = find(pa[i]); } void unite(int a, int b ){ a = find(a); b = find(b); if(a == b)return; if(nh[a] < nh[b])swap(a,b); pa[b]=a; nh[a]+=nh[b];gru--; } int tam(int a ){ return nh[find(a)]; } }; struct query{ int op,a,b; }; int main(){cin.tie(0)->sync_with_stdio(0); int n,m; cin >> n >> m; fo(i,m){ int a,b,w; cin >> a >> b >> w; eventos.pb({w,a,b,i}); graph[a].pb({b,w}); graph[b].pb({a,w}); } int q; cin >> q; int con = 0; vector<query> queries; fo(i,q){ int op; cin >> op; if(op==2) con++; int nodo, peso; cin >> nodo >> peso; queries.pb({op,nodo,peso}); eventos.pb({peso, nodo,-1,i}); } if(con == q){// No hay updates sort(all(eventos), ord); dsu ami(n); for(auto e : eventos){ if(e.b == -1){ res[e.i] = ami.tam(e.a); }else{ ami.unite(e.a,e.b); } } fo(i,q)cout << res[i] << endl; }else if (m==n-1){ }else{ } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...