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

• 問題: No.416 旅行会社
• ユーザー: tails
• 提出日時: 2020-11-05 21:24:08
• 言語: cLay (20240104-1)
• 結果: AC
• 実行時間: 102 ms / 4,000 ms
• コード長: 819 bytes
• コンパイル時間: 3,256 ms
• コンパイル使用メモリ: 167,604 KB
• 実行使用メモリ: 13,068 KB
• 最終ジャッジ日時: 2023-08-21 10:38:58
• 合計ジャッジ時間: 5,122 ms
• ジャッジサーバーID （参考情報）: judge15 / judge11

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	25 ms; 10,184 KB
testcase_01	AC	2 ms; 7,412 KB
testcase_02	AC	2 ms; 7,460 KB
testcase_03	AC	3 ms; 7,580 KB
testcase_04	AC	3 ms; 7,468 KB
testcase_05	AC	3 ms; 7,476 KB
testcase_06	AC	2 ms; 7,480 KB
testcase_07	AC	2 ms; 7,592 KB
testcase_08	AC	3 ms; 7,648 KB
testcase_09	AC	7 ms; 8,052 KB
testcase_10	AC	31 ms; 10,248 KB
testcase_11	AC	33 ms; 13,068 KB
testcase_12	AC	34 ms; 12,980 KB
testcase_13	AC	27 ms; 12,976 KB
testcase_14	AC	99 ms; 11,164 KB
testcase_15	AC	100 ms; 11,644 KB
testcase_16	AC	102 ms; 12,096 KB
testcase_17	AC	100 ms; 11,484 KB
testcase_18	AC	99 ms; 11,376 KB
testcase_19	AC	58 ms; 11,016 KB
testcase_20	AC	56 ms; 10,544 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));
}