結果

問題 No.416 旅行会社
ユーザー 夜夜
提出日時 2021-08-06 18:24:57
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 1,958 bytes
コンパイル時間 999 ms
コンパイル使用メモリ 106,288 KB
実行使用メモリ 814,044 KB
最終ジャッジ日時 2024-09-17 00:30:56
合計ジャッジ時間 5,279 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_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 = vec[x1].size() - 1; j >= 0; j--) {
				vec[y1].emplace_back(vec[x1][j]);
				vec[x1].pop_back();
			}
		}
	}
	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 = vec[x1].size() - 1; j >= 0; j--) {
				vec[y1].emplace_back(vec[x1][j]);
				vec[x1].pop_back();
			}
		}

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