제출 #453221

#제출 시각아이디문제언어결과실행 시간메모리
453221Evirir다리 (APIO19_bridges)C++17
14 / 100
3077 ms8748 KiB
#include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> using namespace std; //using namespace __gnu_pbds; #pragma GCC optimize("O3") #define watch(x) cout<<(#x)<<"="<<(x)<<'\n' #define mset(d,val) memset(d,val,sizeof(d)) #define setp(x) cout<<fixed<<setprecision(x) #define sz(x) (int)(x).size() #define all(x) begin(x), end(x) #define forn(i,a,b) for(int i=(a);i<(b);i++) #define fore(i,a,b) for(int i=(a);i<=(b);i++) #define pb push_back #define F first #define S second #define fbo find_by_order #define ook order_of_key typedef long long ll; typedef long double ld; typedef pair<ll,ll> ii; typedef vector<ll> vi; typedef vector<ii> vii; //template<typename T> //using pbds = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; void SD(int t=0){ cout<<"PASSED "<<t<<endl; } const ll INF = ll(1e18); const int MOD = 998244353; const bool DEBUG = 0; const int MAXN = 50005; const int MAXM = 100005; const int MAXQ = 100005; struct Edge { int u,v; ll w; bool operator<(const Edge &e){ return w<e.w; } }; struct DSU { struct Node{ int p; int sz; }; vector<Node> dsu; int cc; vector<pair<int,Node>> upd; // (v,(p,sz)) DSU(int n){ dsu.resize(n); cc=n; upd.clear(); forn(i,0,n) dsu[i]={i,1}; } inline int rt(int u){ return u==dsu[u].p ? u : rt(dsu[u].p); } inline bool sameset(int u, int v){ return rt(u)==rt(v); } void merge(int u, int v){ u=rt(u); v=rt(v); if(u==v) return; if(dsu[u].sz<dsu[v].sz) swap(u,v); upd.pb({v,dsu[v]}); dsu[v].p=u; dsu[u].sz+=dsu[v].sz; cc--; } void undo() { assert(!upd.empty()); auto u=upd.back(); int p=dsu[u.F].p; dsu[p].sz-=u.S.sz; dsu[u.F]=u.S; upd.pop_back(); } inline Node& operator[](int u){ return dsu[u]; } }; int n,m,Q; vector<Edge> edges; vector<pair<ii,int>> queries; //(node,weight), time vector<pair<ii,int>> updates; // (edge id, new w), time int ans[MAXQ]; bool chg[MAXM]; ll neww[MAXM]; bool cmp(pair<ii,int> &a, pair<ii,int> &b){ return a.F.S>b.F.S; } bool cmptime(pair<ii,int> &a, pair<ii,int> &b){ return a.S<b.S; } void process() { vector<Edge> fixed; forn(i,0,m) { if(!chg[i]) fixed.pb(edges[i]); else updates.pb({{i,edges[i].w},-1}); } sort(all(fixed)); sort(all(updates),cmptime); sort(all(queries),cmp); DSU dsu(n); // large w to small w for(auto q: queries) { int u=q.F.F; ll w=q.F.S; int qtime=q.S; while(!fixed.empty() && fixed.back().w>=w) { dsu.merge(fixed.back().u, fixed.back().v); fixed.pop_back(); } vector<int> chgid; for(auto upd: updates) { if(upd.S>qtime) break; chg[upd.F.F]=1; neww[upd.F.F]=upd.F.S; chgid.pb(upd.F.F); } int updcnt=0; for(int id: chgid) { if(neww[id]>=w) { if(dsu.sameset(edges[id].u, edges[id].v)) continue; dsu.merge(edges[id].u, edges[id].v); updcnt++; } } ans[qtime]=dsu[dsu.rt(u)].sz; while(updcnt--) dsu.undo(); for(int id: chgid) chg[id]=0; } forn(i,0,sz(queries)) cout<<ans[i]<<'\n'; for(auto upd: updates) edges[upd.F.F].w=upd.F.S; queries.clear(); updates.clear(); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>m; forn(i,0,m) { int u,v; ll w; cin>>u>>v>>w; u--; v--; edges.pb({u,v,w}); } cin>>Q; int qcnt=0; forn(i,0,Q) { int t; cin>>t; if(t==1) { int id; ll w; cin>>id>>w; id--; updates.pb({{id,w},sz(queries)}); chg[id]=1; } else { int u; ll w; cin>>u>>w; u--; queries.pb({{u,w},sz(queries)}); } if(qcnt*qcnt>=Q || i==Q-1) process(); } return 0; }
#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...