結果

問題 No.416 旅行会社
コンテスト
ユーザー tails
提出日時 2020-11-05 21:24:08
言語 cLay
(20241019-1)
結果
AC  
実行時間 104 ms / 4,000 ms
コード長 819 bytes
コンパイル時間 2,746 ms
コンパイル使用メモリ 180,744 KB
実行使用メモリ 11,904 KB
最終ジャッジ日時 2024-12-14 20:57:36
合計ジャッジ時間 5,057 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

long ab[200000];
long cd[200000];
char xx[200000];

int en[100001];
int ei[100001];
int eb[400000];

int z[100001];

int d;
void f(int i){
	if(!z[i]){
		z[i]=d;
		for(int k=0;k<en[i];++k){
			f(eb[ei[i]+k]);
		}
	}
}

{
	int @n,@m,@q;
	rep(i,m){
		int @a,@b;
		ab[i]=(long)a<<32|b;
		++en[a];
		++en[b];
	}
	{
		int s=0;
		rep(j,1,n+1){
			ei[j]=s;
			s+=en[j];
			en[j]=0;
		}
	}
	sort(ab,ab+m);
	rep(i,q){
		int @c,@d;
		cd[i]=(long)c<<32|d;
		int dbgk=lower_bound(ab,ab+m,cd[i])-ab;
		xx[lower_bound(ab,ab+m,cd[i])-ab]=1;
	}
	rep(i,m){
		if(!xx[i]){
			int a=ab[i]>>32;
			int b=ab[i];
			eb[ei[a]+en[a]++]=b;
			eb[ei[b]+en[b]++]=a;
		}
	}
	d=-1;
	f(1);
	rrep(i,q){
		d=i+1;
		int a=cd[i]>>32;
		int b=cd[i];
		if(z[a]) f(b);
		if(z[b]) f(a);
		eb[ei[a]+en[a]++]=b;
		eb[ei[b]+en[b]++]=a;
	}
	wtLn(((z+2))(n-1));
}
0