64512023-11-30 16:16:33genf2Tom és Jerry2 (60)cpp17Wrong answer 18/6054ms20164 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define double long double

#define pii pair<int, int>

void cut_nodes_dfs(const auto& g, auto& r, auto& b, auto& v, int i) {
	int m = -1;
	b[i] = r[i];
	for (int j : g[i]) {
		if (r[j] == -1) {
			r[j] = r[i] + 1;
			cut_nodes_dfs(g, r, b, v, j);
			m = max(m, b[j]);
			b[i] = min(b[i], b[j]);
		}
		else {
			b[i] = min(b[i], r[j]);
		}
	}
	if (m >= r[i]) {
		v[i] = true;
	}
	if (m != -1) {
		b[i] = min(b[i], m);
	}
}

void cut_nodes_flood_dfs(const auto& g, auto& v, int i) {
	for (int j : g[i]) {
		if (v[j] || j == 0) {
			continue;
		}
		v[j] = true;
		cut_nodes_flood_dfs(g, v, j);
	}
}

void cut_nodes(const auto& g, auto& v) {
	int N = g.size();
	vector<int> r(N, -1);
	vector<int> b(N);
	r[0] = 0;
	cut_nodes_dfs(g, r, b, v, 0);
	if (v.back() == 0) {
		vector<int> w(N);
		w[g[0].back()] = true;
		cut_nodes_flood_dfs(g, w, g[0].back());
		if (count(w.begin(), w.end(), true) == N - 1) {
			v.pop_back();
		}
	}
	if (count(r.begin(), r.end(), -1) > 0) {
		exit(1);
	}
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
#ifdef CB
	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
#endif
	int N, M, T, DB, E;
	cin >> N >> M >> T >> DB >> E;
	T--, E--;
	vector<vector<int>> gj(N);
	vector<vector<int>> gt(N);
	for (int i = 0; i < M; i++) {
		int a, b, s;
		cin >> a >> b >> s;
		a--, b--;
		gj[a].push_back(b);
		gj[b].push_back(a);
		if (s == 2) {
			gt[a].push_back(b);
			gt[b].push_back(a);
		}
	}
	vector<int> dt(N, -1);
	deque<int> q;
	dt[T] = 0;
	q.push_back(T);
	while (!q.empty()) {
		int i = q.front();
		q.pop_front();
		for (int j : gt[i]) {
			if (dt[j] == -1 && j != E) {
				dt[j] = dt[i] + 1;
				q.push_back(j);
			}
		}
	}
	vector<int> w(N);
	cut_nodes(gj, w);
	vector<int> dj(N, -1);
	vector<int> mj(N, INT_MAX);
	vector<int> mk(N, -1);
	dj[E] = 0;
	q.push_back(E);
	while (!q.empty()) {
		int i = q.front();
		q.pop_front();
		for (int j : gj[i]) {
			if (dj[j] == -1) {
				dj[j] = dj[i] + 1;
				mj[j] = mj[i] - 1;
				mk[j] = mk[i];
				if (w[j] && dt[j] < mj[j]) {
					mj[j] = dt[j];
					mk[j] = j;
				}
				q.push_back(j);
			}
		}
	}
	while (DB--) {
		int i;
		cin >> i;
		i--;
		cout << (mj[i] > 0 ? 0 : mk[i] + 1) << '\n';
	}
	return 0;
}
SubtaskSumTestVerdictTimeMemory
base18/60
1Accepted0/03ms1980 KiB
2Wrong answer0/010ms5576 KiB
3Accepted2/23ms2204 KiB
4Wrong answer0/23ms2440 KiB
5Wrong answer0/23ms2524 KiB
6Wrong answer0/33ms2536 KiB
7Wrong answer0/23ms2820 KiB
8Wrong answer0/23ms3012 KiB
9Wrong answer0/23ms3004 KiB
10Wrong answer0/33ms3156 KiB
11Wrong answer0/33ms3184 KiB
12Wrong answer0/34ms3656 KiB
13Wrong answer0/37ms4792 KiB
14Wrong answer0/38ms5336 KiB
15Wrong answer0/39ms6048 KiB
16Wrong answer0/310ms6612 KiB
17Accepted3/312ms8692 KiB
18Accepted3/321ms14392 KiB
19Wrong answer0/435ms14348 KiB
20Wrong answer0/454ms20076 KiB
21Accepted5/528ms17820 KiB
22Accepted5/530ms20164 KiB