QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#635752 | #9459. Tree Equation | ucup-team4906# | AC ✓ | 667ms | 21128kb | C++20 | 3.1kb | 2024-10-12 20:51:24 | 2024-10-13 18:42:44 |
Judging History
answer
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
const ull mask = std::chrono::steady_clock::now().time_since_epoch().count();
using namespace std;
#define N 100010
ull shift(ull x) {
x ^= mask;
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
x ^= mask;
return x;
}
int na, nb, nc;
bool flag = 0;
vector<int>ea[N], eb[N], ec[N];
vector<int>D[N];
int sz[N];
ull hsh[N];
// ull get_hash(int u, int f) {
// ull res = 1;
// for(auto v : ed[u]) {
// if(v == f) continue;
// res += shift(get_hash(v, u));
// }
// return res;
// }
ull dfs(int u)
{
ull res = 1; sz[u] = 1;
for (int v : ec[u])
{
res += shift(dfs(v));
sz[u] += sz[v];
}
D[sz[u]].push_back(u);
// cout << "???"
return hsh[u] = res;
}
void DFS(int u, int fid, int &n, vector<int>&a)
{
++ n; a.push_back(fid);
int id = n;
for (int v : ec[u]) DFS(v, id, n, a);
}
ull Aval(int u, ull w)
{
ull res = w;
for (int v : ea[u])
{
res += shift(Aval(v, w));
}
return res;
}
ull Bval(int u, ull w)
{
ull res = w;
for (int v : eb[u])
{
res += shift(Bval(v, w));
}
return res;
}
int ck(int u)
{
int p = sz[u];
// cout << "???:" << p << endl;
if ((1LL * p * na > nc) || (nc + 1 - p * na) % nb) return -1;
int q = (nc + 1 - p * na) / nb;
// cout << "GG:" << p << ' ' << q << endl;
for (int v : D[q])
{
// cout << "EEE:" << u << ' ' << v << Aval(1, hsh[u]) + Bval(1, hsh[v]) - 1 << ' ' << hsh[1] << endl;
if (Aval(1, hsh[u]) + Bval(1, hsh[v]) - 1 == hsh[1])
{
return v;
}
}
return -1;
}
void sol(int u)
{
int v = ck(u);
if (v != -1)
{
vector<int>A, B;
int n1 = 0, n2 = 0;
DFS(u, 0, n1, A); DFS(v, 0, n2, B);
cout << n1 << ' ' << n2 << '\n';
for (int x : A) {cout << x << ' ';} cout << '\n';
for (int x : B) {cout << x << ' ';} cout << '\n';
flag = 1; return ;
}
for (int v : ec[u])
{
sol(v);
if (flag) return ;
}
}
void sol()
{
cin >> na >> nb >> nc;
for (int i = 1; i <= na; i ++)
{
int x;
cin >> x;
if (x == 0)continue;
else ea[x].push_back(i);
}
for (int i = 1; i <= nb; i ++)
{
int x;
cin >> x;
if (x == 0)continue;
else eb[x].push_back(i);
}
for (int i = 1; i <= nc; i ++)
{
int x;
cin >> x;
if (x == 0)continue;
else ec[x].push_back(i);
}
dfs(1);
sol(1);
if (!flag) {cout << "Impossible\n";}
for (int i = 1; i <= nc; i ++)
{
ea[i].clear(), eb[i].clear(), ec[i].clear();
D[i].clear(); hsh[i] = 0;
}
flag = 0;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T = 1;
cin >> T;
while (T --) sol();
return 0;
}
/*
1
4 3 10
0 1 2 2
0 1 2
0 1 1 3 4 3 6 3 1 9
*/
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5908kb
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: 667ms
memory: 21128kb
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: 1ms
memory: 5840kb
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