結果

問題 No.416 旅行会社
ユーザー vjudge1vjudge1
提出日時 2024-12-22 23:19:11
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 1,849 bytes
コンパイル時間 2,258 ms
コンパイル使用メモリ 178,332 KB
実行使用メモリ 842,752 KB
最終ジャッジ日時 2024-12-22 23:20:00
合計ジャッジ時間 42,940 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 108 ms
63,488 KB
testcase_01 MLE -
testcase_02 AC 27 ms
43,904 KB
testcase_03 MLE -
testcase_04 AC 35 ms
38,784 KB
testcase_05 MLE -
testcase_06 AC 27 ms
38,656 KB
testcase_07 MLE -
testcase_08 AC 31 ms
39,168 KB
testcase_09 MLE -
testcase_10 AC 127 ms
58,240 KB
testcase_11 AC 165 ms
58,348 KB
testcase_12 AC 168 ms
58,344 KB
testcase_13 MLE -
testcase_14 AC 1,565 ms
195,968 KB
testcase_15 TLE -
testcase_16 TLE -
testcase_17 TLE -
testcase_18 TLE -
testcase_19 TLE -
testcase_20 MLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
//#define int long long
using namespace std;
inline int read()
{
   int x=0,f=1;char ch=getchar();
   while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
   while (ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
   return x*f;
}
void write(int x)
{
   if(x<0)putchar('-'),x=-x;
   if(x<10)putchar(x+'0');
   else write(x/10),putchar(x%10+'0');
}
const int N=3e5;
const int mod=1e9+7;
int n,m,q;
int ans[N];
int f[N];
struct node{
	int u,v;
}mp[N],a[N];
vector<int>g[N];
set<int>s[N];
set<int>ss[N];
int root(int x){
	if(f[x]==x)return x;
	int k=root(f[x]);
	for(int i=0;i<g[x].size();i++)if(ss[k].count(g[x][i])==0)g[k].push_back(g[x][i]),ss[k].insert(g[x][i]);
	g[x].clear(); 
	return f[x]=k;
}
signed main(){
//	freopen("evacuate.in","r",stdin);
//	freopen("evacuate.out","w",stdout);
	n=read(),m=read(),q=read();
	for(int i=1;i<=n;i++)f[i]=i,g[i].push_back(i),s[i].insert(i);
	for(int i=1;i<=m;i++)
		mp[i].u=read(),mp[i].v=read(),s[mp[i].u].insert(mp[i].v),s[mp[i].v].insert(mp[i].u);
 	for(int i=1;i<=q;i++)a[i].u=read(),a[i].v=read(),s[a[i].u].erase(a[i].v),s[a[i].v].erase(a[i].u);
 	for(int i=1;i<=n;i++){
 		while(!s[i].empty()){
			int k=*s[i].begin();
			if(f[root(k)]!=root(i)){
			f[root(k)]=root(i);
			int CCC=root(k);
			g[i].push_back(k);
		
		}
 			s[i].erase(k);
		 }
	 }
	 int fa=root(1);
	 for(int i=2;i<=n;i++)
	 if(root(i)==fa)ans[i]=-1;
	 for(int i=q;i>=1;i--){
	 	int x=root(a[i].u);
	 	int y=root(a[i].v);
		int ff=root(1);	
		f[root(x)]=root(y); 
		fa=root(1);
		if(root(a[i].u)==fa){
			int z=fa;
			if(!ans[z])
			ans[z]=i;
			for(int j=0;j<g[z].size();j++){
				if(ans[g[z][j]]==0)ans[g[z][j]]=i;
			}
			g[z].clear();
		}
		else{
			g[root(a[i].u)].push_back(root(a[i].v));
			g[root(a[i].v)].push_back(root(a[i].u));
		}
	 }
	 for(int i=2;i<=n;i++)cout<<ans[i]<<"\n";
  return 0;
}
0