Submission #645995

#TimeUsernameProblemLanguageResultExecution timeMemory
645995Tenis0206Bridges (APIO19_bridges)C++11
100 / 100
2123 ms11288 KiB
#include <bits/stdc++.h> using namespace std; const int bsize = 1000; struct eveniment { int tip,poz,val; }; int n,m,q; pair<int,int> e[100005]; int c[100005]; int new_c[100005]; bool ch[100005]; int rez[100005]; int t[100005]; int rang[100005]; stack<pair<int,int>> st; int reprezentant(int nod) { if(nod==t[nod]) { return nod; } return reprezentant(t[nod]); } void uneste(int x, int y) { x = reprezentant(x); y = reprezentant(y); st.push({x,y}); if(x==y) { return; } if(rang[x] > rang[y]) { t[y] = x; rang[x] += rang[y]; } else { t[x] = y; rang[y] += rang[x]; } } void remove_last() { int x = st.top().first; int y = st.top().second; st.pop(); if(x==y) { return; } if(x==t[y]) { t[y] = y; rang[x] -= rang[y]; } else { t[x] = x; rang[y] -= rang[x]; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin>>n>>m; for(int i=1;i<=m;i++) { int x,y; cin>>x>>y>>c[i]; e[i] = {x,y}; } for(int i=1;i<=n;i++) { t[i] = i; rang[i] = 1; } cin>>q; vector<eveniment> eves; eves.push_back(eveniment{0,0,0}); for(int i=1;i<=q;i++) { eveniment x; cin>>x.tip>>x.poz>>x.val; eves.push_back(x); } for(int l=1;l<=q;l+=bsize) { int r = min(q,l + bsize - 1); vector<pair<pair<int,int>,int>> queries; vector<pair<pair<int,int>,int>> sp_upd; vector<pair<int,pair<int,int>>> upd; for(int i=l;i<=r;i++) { if(eves[i].tip==2) { queries.push_back({{eves[i].val,eves[i].poz},i}); } else { ch[eves[i].poz] = true; sp_upd.push_back({{eves[i].poz, eves[i].val},i}); } } for(int i=1;i<=m;i++) { if(!ch[i]) { upd.push_back({c[i],{e[i].first,e[i].second}}); } ch[i] = false; } sort(upd.begin(),upd.end(),greater<pair<int,pair<int,int>>>()); sort(queries.begin(),queries.end(),greater<pair<pair<int,int>,int>>()); int poz = 0; for(auto it : queries) { while(poz<upd.size() && upd[poz].first >= it.first.first) { uneste(upd[poz].second.first,upd[poz].second.second); ++poz; } int cnt = 0; for(auto edge : sp_upd) { if(edge.second <= it.second) { new_c[edge.first.first] = edge.first.second; } } for(auto edge : sp_upd) { if(new_c[edge.first.first]==0) { if(c[edge.first.first] >= it.first.first) { uneste(e[edge.first.first].first,e[edge.first.first].second); ++cnt; } continue; } if(new_c[edge.first.first] >= it.first.first) { uneste(e[edge.first.first].first,e[edge.first.first].second); ++cnt; } } for(auto edge : sp_upd) { new_c[edge.first.first] = 0; } rez[it.second] = rang[reprezentant(it.first.second)]; while(cnt) { remove_last(); --cnt; } } while(!st.empty()) { remove_last(); } for(int i=l;i<=r;i++) { if(eves[i].tip==1) { c[eves[i].poz] = eves[i].val; } } } for(int i=1;i<=q;i++) { if(eves[i].tip==2) { cout<<rez[i]<<'\n'; } } return 0; }

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:134:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |             while(poz<upd.size() && upd[poz].first >= it.first.first)
      |                   ~~~^~~~~~~~~~~
#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...