結果

問題 No.416 旅行会社
ユーザー vjudge1vjudge1
提出日時 2024-12-22 17:15:50
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,709 bytes
コンパイル時間 2,092 ms
コンパイル使用メモリ 170,804 KB
実行使用メモリ 25,984 KB
最終ジャッジ日時 2024-12-22 17:16:45
合計ジャッジ時間 47,409 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,882 ms
25,528 KB
testcase_01 WA -
testcase_02 AC 2 ms
13,764 KB
testcase_03 AC 2 ms
10,624 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 2,964 ms
23,040 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 TLE -
testcase_15 TLE -
testcase_16 TLE -
testcase_17 TLE -
testcase_18 TLE -
testcase_19 TLE -
testcase_20 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
int x,y,n,m,q,c1=0,c2=0,h[100005],hd[100005],f[100005],ans[100005];
struct nd{
	int u,v,nxt,num,tg;
}e1[400005],e2[400005];
int fd(int q){
	if(f[q]==q) return q;
	return fd(f[q]);
}
int fans(int q){
	if(f[q]==q&&q==1) return -1;
	if(f[q]==q) return 0;
	if(ans[q]) return ans[q];
	return ans[q]=fans(f[q]);
}
void jb(int u,int v,int ad){
	if(!ad){
		e1[++c1].u=u;
		e1[c1].v=v;
		e1[c1].nxt=h[u];
		h[u]=c1;
	}else{
		e2[++c2].u=u;
		e2[c2].v=v;
		e2[c2].nxt=hd[u];
		hd[u]=c2;
		e2[c2].num=ad;
	}
}
bool cmp(nd a,nd b){
	if(a.u==b.u) return a.v<b.v;
	return a.u<b.u;
}
bool cmp2(nd a,nd b){
	return a.num>b.num;
}
signed main(){
	cin>>n>>m>>q;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		jb(x,y,0);
		jb(y,x,0);
	}for(int i=1;i<=q;i++){
		scanf("%d%d",&x,&y);
		jb(x,y,i);
		jb(y,x,i);
	}sort(e1+1,e1+m*2+1,cmp);
	sort(e2+1,e2+q*2+1,cmp);
	for(int i=1,j=1;i<=q*2;i++,j++){
		if(e1[j].u==e2[i].u&&e1[j].v==e2[i].v) e1[j].tg=e1[j].tg=0;
		else{
			while(e1[j].u!=e2[i].u||e1[j].v!=e2[i].v){
				e1[j].tg=1;
				j++;
			}e1[j].tg=0;
		}
	}for(int i=1;i<=n;i++) f[i]=i;
	for(int i=1;i<=n;i++) ans[i]=0;
	for(int i=1;i<=m*2;i++){
		if(e1[i].tg){
			int u=e1[i].u,v=e1[i].v,fu=fd(u),fv=fd(v),f1=fd(1);
			if(fu==f1||fv==f1) ans[u]=ans[v]=-1;
			f[fu]=fv;
		}
	}sort(e2+1,e2+q*2+1,cmp2);
	for(int i=1;i<=q*2;i++){
		int u=e2[i].u,v=e2[i].v,fu=fd(u),fv=fd(v),f1=fd(1);
//		if(u==2||v==2) cout<<u<<" "<<v<<" "<<fu<<" "<<fv<<" "<<f1<<"\n";
		if(fu==f1){
			if(!ans[v]) ans[v]=e2[i].num;
			if(!ans[u]) ans[u]=fans(u);
		}else if(fv==f1){
			if(!ans[u]) ans[u]=e2[i].num;
			if(!ans[v]) ans[v]=fans(v);
		}
		f[fv]=fu;
	}
	for(int i=2;i<=n;i++) printf("%d\n",ans[i]);
}
0