제출 #552767

#제출 시각아이디문제언어결과실행 시간메모리
552767jjaewon다리 (APIO19_bridges)C++14
0 / 100
1942 ms7824 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 700 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?type<p.type:d<p.d; } }edge[100010]; vector<DATA> query; int N,M,Q,ans[100010]; int p[50010],sz[50010]; 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) flag=1; if(j.type==1){ if((!flag&&j.d>=i.d)||(flag&&edge[j.u].d>=i.d)) merge(edge[j.u].u,edge[j.u].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; query.push_back({t,i,a,0,b}); if(i%SZ==0){ solve(); for(auto j:query) if(j.type==1) edge[j.u].d=j.v; query.clear(); } } solve(); for(int i=1;i<=Q;i++) if(ans[i]>0) cout<<ans[i]<<endl; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

bridges.cpp: In function 'void solve()':
bridges.cpp:60:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |                 auto [x,y]=st.top();
      |                      ^
#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...