結果

問題 No.416 旅行会社
ユーザー vjudge1vjudge1
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 97 ms
16,432 KB
testcase_01 AC 4 ms
5,888 KB
testcase_02 AC 3 ms
6,016 KB
testcase_03 AC 3 ms
6,144 KB
testcase_04 AC 4 ms
6,144 KB
testcase_05 AC 3 ms
6,016 KB
testcase_06 AC 4 ms
6,016 KB
testcase_07 AC 5 ms
5,888 KB
testcase_08 AC 6 ms
6,144 KB
testcase_09 AC 17 ms
7,168 KB
testcase_10 AC 128 ms
16,560 KB
testcase_11 AC 128 ms
16,828 KB
testcase_12 AC 141 ms
16,956 KB
testcase_13 AC 103 ms
16,820 KB
testcase_14 AC 361 ms
23,188 KB
testcase_15 AC 333 ms
23,360 KB
testcase_16 AC 334 ms
23,596 KB
testcase_17 AC 324 ms
23,552 KB
testcase_18 AC 325 ms
23,548 KB
testcase_19 AC 205 ms
17,152 KB
testcase_20 AC 207 ms
16,896 KB
権限があれば一括ダウンロードができます

ソースコード

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