結果

問題 No.416 旅行会社
ユーザー 小夫
提出日時 2025-03-30 14:29:37
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 315 ms / 4,000 ms
コード長 1,754 bytes
コンパイル時間 2,466 ms
コンパイル使用メモリ 214,020 KB
実行使用メモリ 17,628 KB
最終ジャッジ日時 2025-03-30 14:29:44
合計ジャッジ時間 7,415 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define dg pair<int,int>
#define a first
#define b second
#define mk(x,y) make_pair(x,y)
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<<1)+(x<<3)+(ch&15);
		ch=getchar();
	}
	return x*f;
}
inline void write(int x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>9)write(x/10);
	putchar(x%10+'0');
	return;
}
int tot,fa[100010],ans[100010];
vector<int>tp[100010];
dg qry[200010];
set<dg>edge;
inline int findfa(int x){return !fa[x]?x:fa[x]=findfa(fa[x]);}
inline bool find(int x,int y){return findfa(x)==findfa(y); }
inline void merge(int x,int y)
{
	x=findfa(x),y=findfa(y);
	if(x==y)return;
	if(fa[x]>fa[y])swap(x,y);
	fa[x]+=fa[y];
	fa[y]=x;
}
int main()
{
	int n=read(),m=read(),q=read();
	for(int i=1;i<=m;++i)
	{
		int u=read(),v=read();
		if(u>v)swap(u,v);
		edge.insert(mk(u,v));
	}
	for(int i=1;i<=q;++i)
	{
		int u=read(),v=read();
		if(u>v)swap(u,v);
		edge.erase(mk(u,v));
		qry[i]=mk(u,v);
	}
	for(auto syh:edge)merge(syh.a,syh.b);
	for(int i=1;i<=n;++i)
		if(find(1,i))
			ans[i]=-1;
	for(int i=1;i<=n;++i)tp[findfa(i)].emplace_back(i);
	for(int i=q;i;--i)
	{
		int x=findfa(qry[i].a),y=findfa(qry[i].b);
		if(x==y)continue;
		if(find(1,y))swap(x,y);
		if(find(1,x))
			for(auto t:tp[y])
				ans[t]=i;
		if(tp[x].size()<tp[y].size())swap(tp[x],tp[y]);
		tp[x].insert(tp[x].end(),tp[y].begin(),tp[y].end());
		tp[y].clear();
		merge(x,y);
		swap(tp[findfa(x)],tp[x]);
	}
	for(int i=1;i<n;++i)write(ans[i+1]),puts("");
	return 0;
}
/*
6 7 5
1 2
1 6
2 4
2 3
3 5
4 5
5 6
2 3
2 4
1 2
4 5
1 6
*/
0