QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#719686 | #9459. Tree Equation | Estelle_N | AC ✓ | 177ms | 26124kb | C++14 | 2.7kb | 2024-11-07 08:02:04 | 2024-11-07 08:02:04 |
Judging History
answer
#include <cstdio>
#include <chrono>
#include <vector>
#include <algorithm>
#include <functional>
#include <unordered_map>
#define ull unsigned long long
using namespace std;
const int N = 100005;
const int mask = chrono::steady_clock::now().time_since_epoch().count();
ull shift(ull x)
{
x ^= mask;
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
x ^= mask;
return x;
}
struct Tree
{
ull f[N];
int n, Max, dep[N], siz[N];
vector <int> e[N];
void Hash(int u, ull x)
{
f[u] = x;
for(int v : e[u])
Hash(v, x), f[u] += shift(f[v]);
}
void Input()
{
Max = 0;
for(int i = 1; i <= n; ++ i)
e[i].clear();
for(int i = 1, x; i <= n; ++ i)
{
scanf("%d", &x);
if(x)
e[x].push_back(i);
}
}
void Init(int u, int fa)
{
siz[u] = 1;
dep[u] = dep[fa] + 1;
Max = max(Max, dep[u]);
for(int v : e[u])
Init(v, u), siz[u] += siz[v];
}
int cnt = 0;
void Print(int u, int fa)
{
printf("%d ", fa);
int id = ++ cnt;
for(int v : e[u])
Print(v, id);
}
};
Tree A, B, C;
unordered_map <ull, int> vis[2];
vector < pair <ull, int> > val[2];
void work()
{
vis[0].clear();
vis[1].clear();
val[0].clear();
val[1].clear();
scanf("%d%d%d", &A.n, &B.n, &C.n);
A.Input(), A.Init(1, 0);
B.Input(), B.Init(1, 0);
C.Input(), C.Init(1, 0);
C.Hash(1, 1);
for(int i = 1; i <= C.n; ++ i)
{
if(C.dep[i] == A.Max && !vis[0][C.f[i]])
{
vis[0][C.f[i]] = 1;
A.Hash(1, C.f[i]);
val[0].push_back({A.f[1], i});
}
if(C.dep[i] == B.Max && !vis[1][C.f[i]])
{
vis[1][C.f[i]] = 1;
B.Hash(1, C.f[i]);
val[1].push_back({C.f[1] + 1 - B.f[1], i});
}
}
sort(val[0].begin(), val[0].end());
sort(val[1].begin(), val[1].end());
for(int i = 0, j = 0; i < val[0].size(); ++ i)
{
while(j < val[1].size() && val[0][i].first > val[1][j].first)
++ j;
if(j < val[1].size() && val[0][i].first == val[1][j].first)
{
int u = val[0][i].second, v = val[1][j].second;
printf("%d %d\n", C.siz[u], C.siz[v]);
C.Print(u, C.cnt = 0), printf("\n");
C.Print(v, C.cnt = 0), printf("\n");
return;
}
}
printf("Impossible\n");
}
int T;
int main()
{
scanf("%d", &T);
while(T --)
work();
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 15108kb
input:
2 2 3 10 0 1 0 1 2 0 1 1 3 4 3 6 3 1 9 4 3 10 0 1 2 2 0 1 2 0 1 1 3 4 3 6 3 1 9
output:
Impossible 2 1 0 1 0
result:
ok 2 cases passed
Test #2:
score: 0
Accepted
time: 177ms
memory: 26124kb
input:
11122 3 3 11 0 1 1 0 1 1 0 1 1 1 4 4 1 1 8 8 1 7 2 10 0 1 2 2 2 1 1 0 1 0 1 2 1 1 5 5 5 1 1 7 8 14 0 1 2 1 1 1 1 0 1 2 1 1 1 1 1 0 1 1 3 1 1 1 1 1 1 1 11 1 1 4 8 11 0 1 1 1 0 1 1 1 1 1 6 6 0 1 1 1 1 1 6 6 1 1 1 3 4 13 0 1 1 0 1 1 1 0 1 1 3 1 5 1 1 8 1 10 1 12 11 2 14 0 1 2 1 4 4 4 1 1 1 1 0 1 0 1 1 ...
output:
1 3 0 0 1 1 1 2 0 0 1 1 1 0 0 1 1 0 0 2 2 0 1 0 1 1 2 0 0 1 1 5 0 0 1 2 1 1 1 1 0 0 8 2 0 1 1 3 3 3 1 1 0 1 1 1 0 0 4 1 0 1 1 1 0 3 1 0 1 1 0 5 1 0 1 2 1 1 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 2 1 0 1 0 1 5 0 0 1 1 1 1 1 1 0 0 1 3 0 0 1 1 1 2 0 0 1 3 1 0 1 1 ...
result:
ok 11122 cases passed
Test #3:
score: 0
Accepted
time: 3ms
memory: 14772kb
input:
1 5 5 49 0 1 1 3 1 0 1 2 1 2 0 1 2 3 4 1 6 7 8 9 1 11 12 13 14 11 16 17 18 19 1 21 22 23 24 1 26 26 1 1 30 31 31 30 30 35 36 36 35 30 40 41 41 40 1 45 46 46 45
output:
5 5 0 1 2 3 4 0 1 2 2 1
result:
ok 1 cases passed
Extra Test:
score: 0
Extra Test Passed