QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#495070#3025. AssimilationPetroTarnavskyi#RE 0ms0kbC++202.7kb2024-07-27 18:28:412024-07-27 18:28:42

Judging History

你现在查看的是最新测评结果

  • [2024-07-27 18:28:42]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-07-27 18:28:41]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

VI bfs(int n, const vector<VI>& g, int s)
{
	VI d(n, -1);
	d[s] = 0;
	queue<int> q;
	q.push(s);
	while (!q.empty())
	{
		int v = q.front();
		q.pop();
		for (int to : g[v])
			if (d[to] == -1)
			{
				d[v] = d[to] + 1;
				q.push(to);
			}
	}
	return d;
}

void dfs1(const vector<VI>& g, int v, vector<PII>& h, VI& bestSon, VI& par)
{
	h[v] = {0, v};
	for (int to : g[v])
	{
		if (to == par[v])
			continue;
		par[to] = v;
		dfs1(g, to, h, bestSon, par);
		if (h[to].F + 1 > h[v].F)
		{
			h[v] = {h[to].F + 1, h[to].S};
			bestSon[v] = to;
		}
	}
}

void dfs2(const vector<VI>& g, int v, VI& par)
{
	for (int to : g[v])
	{
		if (to == par[v])
			continue;
		par[to] = v;
		dfs2(g, to, par);
	}
}

tuple<bool, vector<PII>, int> f(int n, const vector<VI>& g, int a, int b, int v)
{
	vector<PII> h(n);
	VI bestSon(n, -1);
	VI par(n);
	par[v] = -1;
	dfs1(g, v, h, bestSon, par);
	VI used(n);
	vector<PII> res;
	while (a != v && b != v)
	{
		if (used[h[a].S])
		{
			return {false, {}, -1};
		}
		used[h[a].S] = true;
		while (h[a].F > 0 && b != v)
		{
			res.PB({bestSon[a], b});
			a = bestSon[a];
			b = par[b];
		}
		swap(a, b);
	}
	return {true, res, a ^ b ^ v};
}

void solve()
{
	int n;
	cin >> n;
	vector<VI> g(n);
	FOR(i, 0, n - 1)
	{
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		g[u].PB(v);
		g[v].PB(u);
	}
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	a--;
	b--;
	c--;
	d--;
	VI dA = bfs(n, g, a), dB = bfs(n, g, b), dC = bfs(n, g, c), dD = bfs(n, g, d);
	int v = -1, w = -1;
	FOR(i, 0, n)
	{
		if (dA[i] + dB[i] == dA[b] && (v == -1 || dC[i] < dC[v]))
		{
			v = i;
		}
		if (dC[i] + dD[i] == dC[d] && (w == -1 || dA[i] < dA[v]))
		{
			w = i;
		}
	}
	auto [ok1, vec1, x] = f(n, g, a, b, v);
	auto [ok2, vec2, y] = f(n, g, c, d, w);
	if (!ok1 || !ok2)
	{
		cout << "-1\n";
		return;
	}
	VI par(n);
	dfs2(g, y, par);
	VI ans;
	for (auto [z, t] : vec1)
		ans.PB(z);
	while (v != y)
	{
		v = par[v];
		ans.PB(v);
	}
	reverse(ALL(vec2));
	for (auto [z, t] : vec2)
		ans.PB(t);
	assert(SZ(ans) <= 10 * n);
	cout << SZ(ans) << "\n";
	FOR(i, 0, SZ(ans))
	{
		if (i)
			cout << " ";
		cout << ans[i] + 1;
	}
	cout << "\n";
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while (t--)
		solve();
	return 0;
}




详细

Test #1:

score: 0
Runtime Error

input:

29
9 1
1 1 2 1 1 1 1 1 1
4 1
3 2 1 1
5 316660370
269357435 105688553 346785866 295093544 181703417
6 43402885
39947441 27068237 43810814 44913378 40095941 34779892
22 319594
3815194 3056481 6593888 7315914 6593888 4794774 2561877 5256242 4920603 5256242 3606645 864746 1594265 1235578 2361430 2277526...

output:


result: