제출 #230761

#제출 시각아이디문제언어결과실행 시간메모리
230761crackersamdjam다리 (APIO19_bridges)C++14
100 / 100
2596 ms8688 KiB
#pragma GCC optimize("O3") #pragma GCC target("sse4") #include <bits/stdc++.h> #define all(x) (x).begin(), (x).end() #define gc getchar_unlocked() #define pc(x) putchar_unlocked(x) template<typename T> void scan(T &x){x = 0;bool _=0;T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;} template<typename T> void printn(T n){bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=n%10+48;n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);} template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);} template<typename T> void print(T n){printn(n);pc(10);} template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);} constexpr int MM = 1e5+5, SZ = 800; int n, m, q, a[MM], b[MM], c[MM], ans[MM], par[MM], sz[MM]; struct st{ int op, i, w, id; bool operator<(const st &o) const{ return w > o.w; } } all[MM]; inline int find(int x){ while(x != par[x]) x = par[x]; return x; } std::vector<std::pair<int, int>> rm; inline void merge(int x, int y, int keep){ x = find(x), y = find(y); if(x == y) return; if(sz[x] > sz[y]){ int z = x; x = y; y = z; } par[x] = y; sz[y] += sz[x]; if(!keep) rm.emplace_back(x, y); } inline void pop(){ while(rm.size()){ int x = rm.back().first, y = rm.back().second; rm.pop_back(); par[x] = x; sz[y] -= sz[x]; } } inline void reset_dsu(){ for(int i = 1; i <= n; i++){ par[i] = i; sz[i] = 1; } } std::vector<int> e, ord, rmdone, yes; bool used[MM], done[MM]; //used in this group, done in this group int main(){ memset(ans, -1, sizeof ans); scan(n, m); for(int i = 1; i <= m; i++){ scan(a[i], b[i], c[i]); } scan(q); for(int i = 0; i < q; i++){ scan(all[i].op, all[i].i, all[i].w); all[i].id = i; } for(int i = 0; i*SZ < q; i++){ int l = i*SZ, r = (i+1)*SZ; if(r > q) r = q; std::sort(all+l, all+r); reset_dsu(); e.clear(); ord.clear(); for(int j = l; j < r; j++){ if(all[j].op == 1) used[all[j].i] = 1; } //loop edges (each one only once) for(int j = 1; j <= m; j++){ if(used[j]) e.push_back(j); //some else ord.push_back(j); //all } sort(all(ord), [](int x, int y){ return c[x] < c[y]; }); yes.clear(); for(int j = l; j < r; j++) yes.emplace_back(j); sort(all(yes), [](int x, int y){ return all[x].id > all[y].id; }); //already sorted by greatest w for(int j = l; j < r; j++){ if(all[j].op == 2){ //all (prev groups) while(ord.size() and c[ord.back()] >= all[j].w){ int id = ord.back(); ord.pop_back(); merge(a[id], b[id], 1); } //specific to this group for(int k: yes){ if(all[k].op == 1 and all[k].id < all[j].id){ int id = all[k].i; if(!done[id]){ if(all[k].w >= all[j].w) merge(a[id], b[id], 0); done[id] = 1; rmdone.emplace_back(id); } } } //some (prev groups) for(int k: e){ if(!done[k] and c[k] >= all[j].w) merge(a[k], b[k], 0); } ans[all[j].id] = sz[find(all[j].i)]; pop(); while(rmdone.size()){ done[rmdone.back()] = 0; rmdone.pop_back(); } } } reverse(all(yes)); for(int j: yes){ if(all[j].op == 1){ used[all[j].i] = 0; c[all[j].i] = all[j].w; //update for future batches } } } for(int i = 0; i < q; i++){ if(~ans[i]) print(ans[i]); } 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...