QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#495070 | #3025. Assimilation | PetroTarnavskyi# | RE | 0ms | 0kb | C++20 | 2.7kb | 2024-07-27 18:28:41 | 2024-07-27 18:28:42 |
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...