結果

問題 No.416 旅行会社
ユーザー vjudge1
提出日時 2024-12-23 20:31:48
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 966 ms / 4,000 ms
コード長 1,655 bytes
コンパイル時間 3,910 ms
コンパイル使用メモリ 260,824 KB
実行使用メモリ 37,008 KB
最終ジャッジ日時 2024-12-23 20:32:07
合計ジャッジ時間 13,484 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define int long long
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
template<typename T>istream&operator>>(istream&I,vector<T>&v){for(auto&i:v)I>>i;return I;}
template<typename T>ostream&operator<<(ostream&O,vector<T>&v){for(auto&i:v)O<<i<<' ';return O;}
namespace AC{
struct Dsu{
	vector<int>f,r;int si;
	Dsu(int n=0):si(n),f(n),r(n,1){iota(f.begin(),f.end(),0);}
	int&father(int x){return f[x];}
	int size(int x=-1){return x==-1?si:r[find(x)];}
	void clear(){for(int i=0;i<si;i++)f[i]=i,r[i]=1;}
	int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
	void merge(int x,int y){x=find(x),y=find(y),x!=y?r[x]>r[y]?(f[y]=x,r[x]+=r[y]):(f[x]=y,r[y]+=r[x]):0;}
	bool check(int x,int y){return find(x)==find(y);}
};
vector<int>g[100010];
int ans[100010],mark,vis[100010];
void dfs(int u){
	if(vis[u])return;
	vis[u]=1;
	ans[u]=mark;
	for(auto v:g[u])if(!vis[v])dfs(v);
}
void solve(){
	int n,m,q;
	cin>>n>>m>>q;
	Dsu dsu(n+1);
	set<pair<int,int>>mp;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		mp.insert({u,v});
		mp.insert({v,u});
	}
	vector<pair<int,int>>querys;
	for(int i=1;i<=q;i++){
		int u,v;
		cin>>u>>v;
		querys.push_back({u,v});
		mp.erase({u,v});
		mp.erase({v,u});
	}
	for(auto [u,v]:mp)g[u].push_back(v),g[v].push_back(u),dsu.merge(u,v);
	mark=-1,dfs(1);
	for(int i=q-1;i>=0;i--){
		auto[u,v]=querys[i];
		if(dsu.check(u,v))continue;
		if(dsu.check(u,1))mark=i+1,dfs(v);
		if(dsu.check(v,1))mark=i+1,dfs(u);
		dsu.merge(u,v);
		g[u].push_back(v),g[v].push_back(u);
	}
	for(int i=2;i<=n;i++)cout<<ans[i]<<'\n';
}
}
signed main(){
	int t=1;
	//cin>>t;
	while(t--)AC::solve();
}
0