Submission #552752

#TimeUsernameProblemLanguageResultExecution timeMemory
552752jjaewonBridges (APIO19_bridges)C++17
0 / 100
3082 ms11176 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pll; typedef pair<int,int> pii; #define fi first #define se second #define endl '\n' #define y1 holyshit #define all(x) x.begin(),x.end() const int inf=0x3f3f3f3f; #define SZ 300 struct DATA{ //type 0: edge, type 1: query 1, type 2: query 2 int type,idx,u,v,d; bool operator<(const DATA& p) const{ return d<p.d; } }edge[100010]; vector<DATA> query; int N,M,Q,ans[100010]; int p[100010],sz[100010]; stack<pii> st; int find(int x){ return x==p[x]?x:find(p[x]); } bool merge(int x,int y,bool undo){ x=find(x); y=find(y); if(x==y) return 0; if(sz[x]<sz[y]) swap(x,y); sz[x]+=sz[y]; p[y]=x; if(undo) st.push({x,y}); return 1; } void solve(){ vector<DATA> v; bool used[100010]={0}; for(auto i:query){ if(i.type==1) used[i.idx]=1; else if(i.type==2) v.push_back(i); } for(auto i:edge) if(!used[i.idx]) v.push_back(i); sort(all(v)); reverse(all(v)); for(int i=1;i<=N;i++) p[i]=i, sz[i]=1; for(auto i:v){ if(i.type==0) merge(i.u,i.v,0); else{ bool flag=0; for(auto j:query){ if(i.idx==j.idx&&i.type==j.type) flag=1; if(j.type==1){ if((!flag&&j.d>=i.d)||(flag&&edge[j.idx].d>=i.d)) merge(j.u,j.v,1); } } ans[i.idx]=sz[find(i.u)]; while(!st.empty()){ auto [x,y]=st.top(); sz[x]-=sz[y]; p[y]=y; st.pop(); } } } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin>>N>>M; for(int i=1;i<=M;i++){ int u,v,d; cin>>u>>v>>d; edge[i]={0,i,u,v,d}; } cin>>Q; for(int i=1;i<=Q;i++){ int t,a,b; cin>>t>>a>>b; if(t==1) query.push_back({t,i,edge[a].u,edge[a].v,b}); else query.push_back({t,i,a,0,b}); if(i%SZ==0){ solve(); query.clear(); } } solve(); for(int i=1;i<=Q;i++) if(ans[i]>0) cout<<ans[i]<<endl; 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...