結果

問題 No.416 旅行会社
コンテスト
ユーザー 夜
提出日時 2021-08-06 18:09:32
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 1,900 bytes
コンパイル時間 1,096 ms
コンパイル使用メモリ 107,232 KB
実行使用メモリ 814,284 KB
最終ジャッジ日時 2024-09-17 00:30:50
合計ジャッジ時間 7,377 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other MLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <deque>
#include <cstdio>
#include <set>
#include <map>
#include <bitset>
#include <stack>
#include <cctype>
using namespace std;
int par[200020];
set<pair<int, int>> st;
pair<int, int> p[200020], p1[200020];
int ans[200020];
vector<vector<int>> vec(200020);
int root(int x) {
	if (par[x] == x) {
		return x;
	}
	else {
		return par[x] = root(par[x]);
	}
}
int main() {
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 1; i <= n; i++) {
		par[i] = i;
		vec[i].emplace_back(i);
	}
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		p[i] = { a,b };
		st.insert(p[i]);
	}
	for (int i = 0; i < q; i++) {
		int c, d;
		cin >> c >> d;
		p1[i] = { c,d };
		auto itr = st.lower_bound({ c,d });
		st.erase(itr);
	}
	for (auto itr = st.begin(); itr != st.end(); itr++) {
		pair<int, int> now = *itr;
		int x = now.first, y = now.second;
		int x1 = root(x), y1 = root(y);
		if (x1 != y1) {
			par[x1] = y1;
			for (int j = 0; j < vec[x1].size(); j++) {
				vec[y1].emplace_back(vec[x1][j]);
			}
		}
	}
	for (int i = 2; i <= n; i++) {
		if (root(1) == root(i)) {
			ans[i] = -1;
		}
		else {
			ans[i] = 0;
		}
	}
	reverse(p1, p1 + q);
	for (int i = 0; i < q; i++) {
		int x = p1[i].first, y = p1[i].second;
		int x1 = root(x), y1 = root(y);
		if (x1 != y1) {
			if (x1 == root(1)) {
				for (int j = 0; j < vec[y1].size(); j++) {
					if (ans[vec[y1][j]] == 0) {
						ans[vec[y1][j]] = q - i;
					}
				}
			}
			if (y1 == root(1)) {
				for (int j = 0; j < vec[x1].size(); j++) {
					if (ans[vec[x1][j]] == 0) {
						ans[vec[x1][j]] = q - i;
					}
				}
			}
			par[x1] = y1;
			for (int j = 0; j < vec[x1].size(); j++) {
				vec[y1].emplace_back(vec[x1][j]);
			}
		}

	}
	for (int i = 2; i <= n; i++) {
		cout << ans[i] << endl;
	}
}
0