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

• 問題: No.416 旅行会社
• ユーザー: tails
• 提出日時: 2020-11-05 21:46:43
• 言語: cLay (20240104-1)
• 結果: AC
• 実行時間: 74 ms / 4,000 ms
• コード長: 777 bytes
• コンパイル時間: 4,937 ms
• コンパイル使用メモリ: 167,096 KB
• 実行使用メモリ: 13,052 KB
• 最終ジャッジ日時: 2023-08-21 10:41:13
• 合計ジャッジ時間: 5,512 ms
• ジャッジサーバーID （参考情報）: judge12 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	19 ms; 10,200 KB
testcase_01	AC	2 ms; 7,416 KB
testcase_02	AC	2 ms; 7,448 KB
testcase_03	AC	3 ms; 7,488 KB
testcase_04	AC	2 ms; 7,608 KB
testcase_05	AC	2 ms; 7,484 KB
testcase_06	AC	2 ms; 7,412 KB
testcase_07	AC	2 ms; 7,448 KB
testcase_08	AC	3 ms; 7,656 KB
testcase_09	AC	5 ms; 7,796 KB
testcase_10	AC	25 ms; 10,376 KB
testcase_11	AC	27 ms; 12,944 KB
testcase_12	AC	27 ms; 13,052 KB
testcase_13	AC	20 ms; 13,044 KB
testcase_14	AC	71 ms; 11,088 KB
testcase_15	AC	74 ms; 11,664 KB
testcase_16	AC	74 ms; 12,112 KB
testcase_17	AC	72 ms; 11,460 KB
testcase_18	AC	73 ms; 11,364 KB
testcase_19	AC	45 ms; 11,036 KB
testcase_20	AC	43 ms; 10,740 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;
		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));
}