#575902 (cLay) No.416 旅行会社

• 問題: No.416 旅行会社
• ユーザー: tails
• 提出日時: 2020-11-05 21:24:08
• 言語: cLay (20240714-1)
• 結果: AC
• 実行時間: 101 ms / 4,000 ms
• コード長: 819 bytes
• コンパイル時間: 2,369 ms
• コンパイル使用メモリ: 180,564 KB
• 実行使用メモリ: 11,904 KB
• 最終ジャッジ日時: 2024-05-08 15:58:16
• 合計ジャッジ時間: 4,569 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	24 ms; 8,832 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	1 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	1 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	3 ms; 5,376 KB
testcase_09	AC	6 ms; 5,376 KB
testcase_10	AC	31 ms; 8,704 KB
testcase_11	AC	31 ms; 10,496 KB
testcase_12	AC	32 ms; 10,496 KB
testcase_13	AC	25 ms; 10,368 KB
testcase_14	AC	97 ms; 11,264 KB
testcase_15	AC	97 ms; 11,596 KB
testcase_16	AC	101 ms; 11,904 KB
testcase_17	AC	98 ms; 11,340 KB
testcase_18	AC	97 ms; 11,392 KB
testcase_19	AC	56 ms; 9,600 KB
testcase_20	AC	55 ms; 9,216 KB

ソースコード

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));
}