結果

問題 No.416 旅行会社
ユーザー vjudge1
提出日時 2024-12-22 22:49:39
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 361 ms / 4,000 ms
コード長 814 bytes
コンパイル時間 1,735 ms
コンパイル使用メモリ 175,972 KB
実行使用メモリ 23,596 KB
最終ジャッジ日時 2024-12-22 22:49:48
合計ジャッジ時間 6,133 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std; const int N=100010,M=N*2; int U[M],V[M],u[M],v[M],f[N],r[N]; vector<int> p[N]; set<pair<int,int>> s;
void merge(int u,int v,int k){
    u=f[u],v=f[v]; if(u==v) return;
    if(v==1||(u!=1&&p[u].size()<p[v].size())) swap(u,v);
    for(int x:p[v]) f[x]=u,p[u].push_back(x);
    if(u==1) for(int x:p[v]) r[x]=k;
    p[v].clear();
}
int main(){
    int n,m,q; scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;++i) f[i]=i,p[i].push_back(i);
    for(int i=1;i<=m;++i) scanf("%d%d",&U[i],&V[i]);
    for(int i=1;i<=q;++i) scanf("%d%d",&u[i],&v[i]),s.insert({u[i],v[i]});
    for(int i=1;i<=m;++i)
        if(!s.count({U[i],V[i]})&&!s.count({U[i],V[i]})) merge(U[i],V[i],-1);
    for(int i=q;i>=1;--i) merge(u[i],v[i],i);
    for(int i=2;i<=n;++i) printf("%d\n",r[i]); return 0;
}
0