結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 AC 48 ms
87,104 KB
testcase_02 AC 50 ms
87,112 KB
testcase_03 MLE -
testcase_04 AC 48 ms
85,504 KB
testcase_05 AC 48 ms
85,376 KB
testcase_06 AC 49 ms
85,376 KB
testcase_07 AC 48 ms
85,504 KB
testcase_08 AC 52 ms
86,144 KB
testcase_09 AC 67 ms
88,064 KB
testcase_10 AC 155 ms
104,960 KB
testcase_11 AC 207 ms
105,220 KB
testcase_12 AC 214 ms
105,092 KB
testcase_13 MLE -
testcase_14 AC 1,627 ms
242,816 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=7e5;
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