제출 #477977

#제출 시각아이디문제언어결과실행 시간메모리
477977jeroenodb다리 (APIO19_bridges)C++14
73 / 100
3026 ms9044 KiB
#include "bits/stdc++.h" using namespace std; #define all(x) begin(x),end(x) template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; } template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; } #define debug(a) cerr << "(" << #a << ": " << a << ")\n"; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int,int> pi; const int mxN = 1e5+1, oo = 1e9; struct DSU{ vector<int> szpar; int components; DSU(int n) { szpar.assign(n+1,-1); components = n; } void reset() { fill(all(szpar),-1); components=szpar.size()-1; } void link(int a, int b) { components--; if(szpar[a]>szpar[b]) { swap(a,b); } szpar[a] += szpar[b]; szpar[b] = a; } void unite(int a, int b) { int pa = find(a),pb = find(b); if(pa!=pb) { link(pa,pb); } } int find(int a) { if(szpar[a]<0) return a; return szpar[a] = find(szpar[a]); } }; struct mys { bitset<mxN> vis; vi st; bool add(int i) { if(vis[i]) return true; vis[i]=true; st.push_back(i); return false; } void reset() { for(auto i : st) vis[i]=false; st.clear(); } }; struct edge{ int a,b,w; bool operator<(const edge& o) const { return w>o.w; } }; const int B=407; struct query { int t,b,r; }; edge es[mxN]; struct comp{ bool operator()(int a, int b) const {return es[a]<es[b] or (es[a].w==es[b].w and a<b);} }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n,m; cin >> n >> m; for(int i=0;i<m;++i) { auto& e = es[i]; cin >> e.a >> e.b >> e.w; e.a--,e.b--; } int Q; cin >> Q; set<int,comp> order; for(int i=0;i<m;++i) order.insert(i); DSU dsu(n),dsu2(n); mys s,s2,verts; vvi adj(n); vector<query> qs; for(int iter=0;iter<Q;iter+=B) { int len = min(B,Q-iter); qs.resize(len); s.reset(); for(auto& q : qs) { cin >> q.t >> q.b >> q.r; q.b--; if(q.t==1) { s.add(q.b); } } vi rq; rq.reserve(len); for(int i=0;i<len;++i) if(qs[i].t==2) rq.push_back(i); sort(all(rq), [&](int c,int d){return qs[c].r>qs[d].r;}); dsu.reset(); auto it = rq.begin(); auto it2 = order.begin(); while(it!=rq.end()) { if(it2==order.end() or (it!=rq.end() and qs[*it].r>es[*it2].w)) { // do query auto add= [&](int a, int b) { a=dsu.find(a), b=dsu.find(b); if(!verts.add(a)) adj[a].clear(); if(!verts.add(b)) adj[b].clear(); if(a==b) return; adj[a].push_back(b); adj[b].push_back(a); }; s2.reset(); verts.reset(); auto& q = qs[*it]; for(int j=*it-1;j>=0;--j) { if(qs[j].t==1 and !s2.vis[qs[j].b]) { s2.add(qs[j].b); auto& e = es[qs[j].b]; if(qs[j].r>=q.r) add(e.a,e.b); } } for(auto i:s.st) { if(!s2.vis[i]) { auto& e = es[i]; if(e.w>=q.r) add(e.a,e.b); } } int mycomp = dsu.find(q.b); vi st; st.push_back(mycomp); add(mycomp,mycomp); verts.reset(); verts.add(mycomp); q.b=0; while(!st.empty()) { int at = st.back(); st.pop_back(); q.b+=-dsu.szpar[at]; for(int to : adj[at]) if(!verts.vis[to]) { verts.add(to); st.push_back(to); } } ++it; } else { auto& e = es[*it2]; if(!s.vis[*it2]) dsu.unite(e.a,e.b); ++it2; } } for(auto& q : qs) { if(q.t==1) { order.erase(q.b); es[q.b].w = q.r; order.insert(q.b); } else { cout << q.b << '\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...