Submission #568942

#TimeUsernameProblemLanguageResultExecution timeMemory
568942HappyPacManBridges (APIO19_bridges)C++14
0 / 100
3069 ms5272 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 5e4 + 2; vector<tuple<int,int,int> > edge; int dsu[maxn],sz[maxn],res[maxn<<1]; int f(int x){ return dsu[x] == x ? dsu[x] : f(dsu[x]); } void join(int x,int y){ x = f(x), y = f(y); if(x != y){ dsu[x] = y; sz[y] += sz[x]; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n,m; cin >> n >> m; for(int i=1;i<=m;i++){ int u,v,w; cin >> u >> v >> w; edge.emplace_back(-w,u,v); } sort(edge.begin(),edge.end()); int q; cin >> q; vector<tuple<int,int,int> > query; for(int i=1;i<=n;i++){ dsu[i] = i; sz[i] = 1; } for(int i=0;i<q;i++){ int t,x,y; cin >> t >> x >> y; query.emplace_back(-y,x,i); } sort(query.begin(),query.end()); for(int i=0,j=0;i<q;i++){ while(j<m && get<0>(edge[j]) <= get<0>(query[i])){ join(get<1>(edge[j]),get<2>(edge[j])); j++; } res[get<2>(query[i])] = sz[f(get<1>(query[i]))]; } for(int i=0;i<q;i++){ cout << res[i] << '\n'; } }
#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...