結果

問題 No.416 旅行会社
コンテスト
ユーザー vjudge1
提出日時 2024-12-22 17:18:02
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,571 bytes
コンパイル時間 1,869 ms
コンパイル使用メモリ 172,364 KB
実行使用メモリ 20,964 KB
最終ジャッジ日時 2024-12-22 17:18:08
合計ジャッジ時間 5,708 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 21
権限があれば一括ダウンロードができます

ソースコード

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 f[q]=fd(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;
		else if(fv==f1) if(!ans[u]) ans[u]=e2[i].num;
		f[fv]=fu;
	}
//	for(int i=2;i<=n;i++){
//		if(!ans[i]){
//			
//		}
//	}
	for(int i=2;i<=n;i++) printf("%d\n",ans[i]);
}
0