제출 #1033262

#제출 시각아이디문제언어결과실행 시간메모리
1033262ASN49K다리 (APIO19_bridges)C++17
100 / 100
2901 ms20016 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; const int SQRT=230; namespace dsu { static int t[N],sz[N]; vector<int>g[N]; int nr_dfs,last_visit[N]; int root(int x) { if(t[x]!=x) { t[x]=root(t[x]); } return t[x]; } void unite(int x,int y) { x=root(x); y=root(y); if(x==y) { return; } t[y]=x; sz[x]+=sz[y]; } void init(int n) { fill(sz,sz+n,1); iota(t,t+n , 0); } int size(int x) { return sz[root(x)]; } int dfs(int nod) { last_visit[nod]=nr_dfs; int rez=sz[nod]; for(auto &c:g[nod]) { if(last_visit[c]!=nr_dfs) { rez+=dfs(c); } } return rez; } int size_of_comp(int x) { nr_dfs++; return dfs(root(x)); } } //aka goomaxing 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; }; static int n,m,q; static vector<edge>edges; static vector<query>querys; static set<pair<int,int>>mp; int old[N]; 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); bad.reserve(r-l+1); for(auto &c:mp) { if(!appears[c.second]) { good.pb(c.second); } else { bad.pb(c.second); } } for(auto &c:bad) { mp.erase({-edges[c].weight , c}); } vector<int>ord_querys(r-l,0); iota(all(ord_querys) , l); 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::init(n); 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::unite(edges[*it_good].x , edges[*it_good].y); } 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::g[dsu::root(edges[c].x)].pb(dsu::root(edges[c].y)); dsu::g[dsu::root(edges[c].y)].pb(dsu::root(edges[c].x)); } } querys[*it_ord_querys].rez=dsu::size_of_comp(querys[*it_ord_querys].poz); for(auto &c:bad) { if(edges[c].weight>=querys[*it_ord_querys].weight) { dsu::g[dsu::root(edges[c].x)].clear(); dsu::g[dsu::root(edges[c].y)].clear(); } } for(int i=*it_ord_querys-1;i>=l;i--) { if(querys[i].tip==1) { edges[querys[i].poz].weight=old[i-l]; } } } for(int i=l;i<r;i++) { if(querys[i].tip==1) { edges[querys[i].poz].weight=querys[i].weight; } } for(auto &c:bad) { mp.insert({-edges[c].weight , c}); } } 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--; mp.insert({-z , i}); 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--; } for(int i=0;i<q;i+=SQRT) { solve_batch(i,min(i+SQRT,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...