64502023-11-30 16:10:54genf2Tom és Jerry2 (60)cpp17Hibás válasz 18/6052ms24040 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();
		}
	}
}

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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base18/60
1Elfogadva0/03ms1824 KiB
2Hibás válasz0/012ms5840 KiB
3Elfogadva2/23ms2384 KiB
4Hibás válasz0/23ms2620 KiB
5Hibás válasz0/23ms2828 KiB
6Hibás válasz0/33ms3024 KiB
7Hibás válasz0/23ms3400 KiB
8Hibás válasz0/23ms3480 KiB
9Hibás válasz0/23ms3592 KiB
10Hibás válasz0/33ms3824 KiB
11Hibás válasz0/34ms4032 KiB
12Hibás válasz0/34ms4392 KiB
13Hibás válasz0/37ms5584 KiB
14Hibás válasz0/38ms6160 KiB
15Hibás válasz0/39ms6900 KiB
16Hibás válasz0/312ms7648 KiB
17Elfogadva3/312ms9828 KiB
18Elfogadva3/320ms15944 KiB
19Hibás válasz0/435ms16644 KiB
20Hibás válasz0/452ms23004 KiB
21Elfogadva5/528ms21240 KiB
22Elfogadva5/532ms24040 KiB