제출 #1033059

#제출 시각아이디문제언어결과실행 시간메모리
1033059ASN49K다리 (APIO19_bridges)C++14
0 / 100
3074 ms9016 KiB
#define LOCAL 1 #include <bits/stdc++.h> using namespace std; using i64=long long; #define all(x) x.begin(),x.end() #define pb push_back #define UNSET -1 const int N = 50'000; namespace dsu_roll_back { vector<int>t,sz; stack<int>sk; void roll_back() { while(sk.size()) { sz[t[sk.top()]]-=sz[sk.top()]; t[sk.top()]=sk.top(); sk.pop(); } } int root(int x) { if(t[x]!=x) { return root(t[x]); } return x; } void unite(int x,int y,bool roll) { x=root(x); y=root(y); if(sz[x]<sz[y]) { swap(x,y); } if(x==y) { return; } t[y]=x; sz[x]+=sz[y]; if(roll) { sk.push(y); } } void init(int n) { t=sz=vector<int>(n,1); iota(all(t) , 0); } int size(int x) { return sz[root(x)]; } } //do not edge kids struct edge { int x,y,weight; bool operator ==(const edge& b)const { return x==b.x && y==b.y && weight==b.weight; } }; struct query { int tip,poz,weight,rez; }; int n,m,q; vector<edge>edges; vector<query>querys; void solve_batch(const int l,const int r) { vector<bool>appears(m,false); for(int i=l;i<r;i++) { if(querys[i].tip==1) { appears[querys[i].poz]=true; } } vector<int>good; vector<int>bad; good.reserve(n); for(int i=0;i<m;i++) { if(!appears[i]) { good.pb(i); } else { bad.pb(i); } } vector<int>ord_querys(r-l,0); iota(all(ord_querys) , l); sort(all(good) , [&](int x,int y){return edges[x].weight>edges[y].weight;}); sort(all(ord_querys) , [&](int x,int y){ if(querys[x].weight==querys[y].weight) { return querys[x].tip<querys[y].tip; } return querys[x].weight>querys[y].weight; }); vector<int>::iterator it_good=good.begin(); vector<int>::iterator it_ord_querys=ord_querys.begin(); dsu_roll_back::init(n); vector<int>old(r-l); for(;it_ord_querys!=ord_querys.end();it_ord_querys++) { if(querys[*it_ord_querys].tip==1) { continue; } for(;it_good!=good.end() && edges[*it_good].weight>=querys[*it_ord_querys].weight;it_good++) { dsu_roll_back::unite(edges[*it_good].x , edges[*it_good].y ,false); } auto old2=edges; for(int i=l;i<*it_ord_querys;i++) { if(querys[i].tip==1) { old[i-l]=edges[querys[i].poz].weight; edges[querys[i].poz].weight=querys[i].weight; } } for(auto &c:bad) { if(edges[c].weight>=querys[*it_ord_querys].weight) { dsu_roll_back::unite(edges[c].x , edges[c].y , true); } } //cout<<dsu_roll_back::size(querys[*it_ord_querys].poz)<<' '<<*it_ord_querys<<'\n'; querys[*it_ord_querys].rez=dsu_roll_back::size(querys[*it_ord_querys].poz); for(int i=l;i<*it_ord_querys;i++) { if(querys[i].tip==1) { edges[querys[i].poz].weight=old[i-l]; assert(edges[querys[i].poz].weight == old2[querys[i].poz].weight); } } assert(old2==edges); dsu_roll_back::roll_back(); } for(int i=l;i<r;i++) { if(querys[i].tip==1) { edges[querys[i].poz].weight=querys[i].weight; } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>n>>m; edges.resize(m); for(int i=0;i<m;i++) { int x,y,z; cin>>x>>y>>z; x--; y--; edges[i]={x,y,z}; } cin>>q; querys.resize(q); for(int i=0;i<q;i++) { cin>>querys[i].tip>>querys[i].poz>>querys[i].weight; querys[i].poz--; } solve_batch(0,q); for(int i=0;i<q;i++) { if(querys[i].tip==2) { cout<<querys[i].rez<<'\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...