結果
問題 | No.416 旅行会社 |
ユーザー |
![]() |
提出日時 | 2018-11-06 17:26:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 487 ms / 4,000 ms |
コード長 | 1,196 bytes |
コンパイル時間 | 1,852 ms |
コンパイル使用メモリ | 205,400 KB |
最終ジャッジ日時 | 2025-01-06 15:40:39 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include<bits/stdc++.h>using namespace std;using Int = long long;template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}//INSERT ABOVE HEREsigned main(){int n,m,q;cin>>n>>m>>q;vector<int> a(m),b(m),c(q),d(q);for(int i=0;i<m;i++) cin>>a[i]>>b[i],a[i]--,b[i]--;for(int i=0;i<q;i++) cin>>c[i]>>d[i],c[i]--,d[i]--;vector<int> ans(n,0),p(n);vector<vector<int> > G(n);for(int i=0;i<n;i++) G[i].emplace_back(i),p[i]=i;auto unite=[&](int x,int y,int k){x=p[x];y=p[y];if(x==y) return;if(y==0) swap(x,y);if(x!=0&&G[x].size()<G[y].size()) swap(x,y);for(int z:G[y]){p[z]=x;G[x].emplace_back(z);if(x==0) ans[z]=k;}G[y].clear();};using P = pair<int, int>;set<P> sp;for(int i=0;i<q;i++) sp.emplace(c[i],d[i]);for(int i=0;i<m;i++){if(sp.count(P(a[i],b[i]))) continue;unite(a[i],b[i],-1);}reverse(c.begin(),c.end());reverse(d.begin(),d.end());for(int i=0;i<q;i++) unite(c[i],d[i],q-i);for(int i=1;i<n;i++) cout<<ans[i]<<endl;return 0;}