結果

問題 No.416 旅行会社
コンテスト
ユーザー vjudge1
提出日時 2024-12-25 22:30:06
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,077 bytes
コンパイル時間 1,750 ms
コンパイル使用メモリ 181,004 KB
実行使用メモリ 30,544 KB
最終ジャッジ日時 2024-12-25 22:30:56
合計ジャッジ時間 39,127 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14 TLE * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define int long long
//#define USE_FREOPEN
//#define MUL_TEST
#define FILENAME "evacuate"
using namespace std;
int ig[100005],ans[100005];
vector<int> gi[100005];
set<pair<int,int> > e;
vector<pair<int,int> > g;

inline int read()
{
	int res = 0,f = 1;
	char c = getchar();
	while (!isdigit(c))
	{
		if (c == '-') f = -1;
		c = getchar();
	}
	while (isdigit(c))
	{
		res = (res << 1) + (res << 3) + (c - 48);
		c = getchar();
	}
	return res * f;
}

void merge(int a,int b)
{
	if (ig[a] == ig[b]) return;
	if (gi[ig[a]].size() < gi[ig[b]].size()) swap(a,b);
	int ga = ig[a],gb = ig[b];
	int glb = gi[gb].size();
	for (int i = 0; i < glb; i++)
	{
		ig[gi[gb][i]] = ga;
		gi[ga].push_back(gi[gb][i]);
	}
	gi[gb].clear();
}

void solve()
{
	int n,m,q;
	cin >> n >> m >> q;
	for (int i = 1; i <= m; i++)
	{
		int u,v;
		cin >> u >> v;
		e.insert(make_pair(u,v));
	}
	for (int i = 1; i <= q; i++)
	{
		int u,v;
		cin >> u >> v;
		e.erase(make_pair(u,v));
		g.push_back(make_pair(u,v));
	}
	for (int i = 1; i <= n; i++)
	{
		ig[i] = i;
		gi[i].push_back(i);
	}
	set<pair<int,int> >::iterator it;
	for (it = e.begin(); it != e.end(); it++)
	{
		int a = it->first,b = it->second;
		merge(a,b);
	}
	int gg = ig[1];
	int gl = gi[gg].size();
	for (int i = 0; i < gl; i++)
		ans[gi[gg][i]] = -1;
	for (int i = q - 1; i >= 0; i--)
	{
		int a = g[i].first,b = g[i].second;
		if (ig[a] != ig[1] && ig[b] != ig[1])
		{
			merge(a,b);
			continue;
		}
		if (ig[a] == ig[1])
		{
			int gb = ig[b];
			int glb = gi[gb].size();
			for (int j = 0; j < glb; j++)
				if (ans[gi[gb][j]] == 0)
					ans[gi[gb][j]] = i + 1;
		}
		else
		{
			int ga = ig[a];
			int gla = gi[ga].size();
			for (int j = 0; j < gla; j++)
				if (ans[gi[ga][j]] == 0)
					ans[gi[ga][j]] = i + 1;
		}
		merge(a,b);
	}
	for (int i = 2; i <= n; i++)
		printf("%lld\n",ans[i]);
}

signed main()
{
	#ifdef USE_FREOPEN
		freopen(FILENAME ".in","r",stdin);
		freopen(FILENAME ".out","w",stdout);
	#endif
	int _ = 1;
	#ifdef MUL_TEST
		cin >> _;
	#endif
	while (_--)
		solve();
	_^=_;
	return (0^_^0);
}
0