QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#720069	#9459. Tree Equation	KellyWLJ	AC ✓	80ms	30996kb	C++17	6.4kb	2024-11-07 10:30:47	2024-11-07 10:30:47

Judging History

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

[2024-11-07 10:30:47]
评测

测评结果：AC
用时：80ms
内存：30996kb

查看

[2024-11-07 10:30:47]
提交

answer

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;

using ull = unsigned long long;
const int N = 100010, SZ = (1 << 18) + 5;
static char buf[SZ], *bgn = buf, *til = buf;
char getc() {
    if(bgn == til)  bgn = buf, til = buf + fread(buf, 1, SZ, stdin);
    return bgn == til ? EOF : *bgn++;
}
template<typename T>
void read(T &x) {
    char ch = getc();  T fh = 0;   x = 0;
    while(ch < '0' || ch > '9')    fh |= (ch == '-'), ch = getc();
    while(ch >= '0' && ch <= '9')   x = x * 10 + ch - '0', ch = getc();
    x = fh ? -x : x;
}
template<typename Type, typename... argc>
void read(Type &x, argc &...args)   {read(x), read(args...);}
template<typename T>
void print(T x) {
    if(x < 0)  putchar('-'), x = -x;
    if(x / 10)  print(x / 10);
    putchar(x % 10 + '0');
}
int flag;
ull F(ull x)   {x ^= x << 13, x ^= x >> 7, x ^= x << 5;    return x;}
struct Tree {
    int n, fa[N], nfa[N], id[N], cnt, siz[N];
    ull f[N], g[N];
    vector<int> edge[N];
    void clear() {
        for(int i = 0; i <= n; ++i) edge[i].clear(), f[i] = g[i] = nfa[i] = siz[i] = 0;
        cnt = 0;
    }
    void input() {
        clear();
        for(int i = 1; i <= n; ++i) read(fa[i]), edge[fa[i]].pb(i);
    }
    void dfs(int x) {
        siz[x] = f[x] = 1;
        for(int y : edge[x])    dfs(y), siz[x] += siz[y], f[x] += F(f[y]);
    }
    void Dfs(int x, ull val) {
        g[x] = val;
        for(int y : edge[x])
            Dfs(y, val), g[x] += F(g[y]);
    }
    void DFS(int x, int lim) {
        id[x] = ++cnt;
        for(int y : edge[x])    if(siz[y] < lim)    DFS(y, lim), nfa[id[y]] = id[x];
    }
    void work() {
        dfs(1);
        for(int i = 1; i <= n; ++i) sort(edge[i].begin(), edge[i].end(), [&](const int x, const int y){return siz[x] < siz[y];});
    }
}a, b, c;
void output(int rtx, int sizx, int rty, int sizy) {
    if(flag)    swap(rtx, rty), swap(sizx, sizy);
    print(sizx), putchar(' '), print(sizy), putchar('\n');
    // cerr << flag << " " << rtx << " " << rty << " " << sizx << " " << sizy << "\n";
    c.cnt = 0, c.DFS(rtx, sizx);
    // cerr << c.cnt << " ";
    for(int i = 1; i <= c.cnt; ++i) print(c.nfa[i]), putchar(' ');
    putchar('\n');
    c.cnt = 0, c.DFS(rty, sizy);
    for(int i = 1; i <= c.cnt; ++i) print(c.nfa[i]), putchar(' ');
    // cerr << c.cnt << "\n";
    putchar('\n');
}
int solve() {
    int tmp = c.edge[1].back(), sizx = 1;   ull hx = 1;
    for(int i = 0; i <= c.edge[tmp].size(); ++i) {
        if(i < c.edge[tmp].size() && c.siz[c.edge[tmp][i]] % sizx) {
            if(i < c.edge[tmp].size())  sizx += c.siz[c.edge[tmp][i]], hx += F(c.f[c.edge[tmp][i]]);
            continue;
        }
        int sizy = max(0ll, (c.n + 1 - 1ll * a.n * sizx) / b.n), rt = 0;
        if(1ll * a.n * sizx + 1ll * b.n * sizy - 1 != c.n || !sizy) {
            if(i < c.edge[tmp].size())  sizx += c.siz[c.edge[tmp][i]], hx += F(c.f[c.edge[tmp][i]]);
            continue;
        }
        multiset<ull> nw;   
        a.Dfs(1, hx);
        for(int x : a.edge[1])  nw.insert(a.g[x]);
        for(int j = 0; j < i; ++j)  nw.insert(c.f[c.edge[tmp][j]]);
        for(int j = (int)c.edge[1].size() - 1; j >= 0; --j) {
            int x = c.edge[1][j];
            if(nw.empty() || nw.find(c.f[x]) == nw.end())   {rt = x;    break;}
            nw.erase(nw.find(c.f[x]));
        }
        // cerr << tmp << " " << rt << " : " << sizx << " " << sizy << "\n";
        if(!rt || rt == tmp || c.siz[rt] % sizy) {
            if(i < c.edge[tmp].size())  sizx += c.siz[c.edge[tmp][i]], hx += F(c.f[c.edge[tmp][i]]);
            continue;
        }
        // cerr << tmp << " " << rt << " : " << sizx << " " << sizy << "\n";
        int nsiz = 1;   ull nhx = 1;
        for(int x : c.edge[rt])
            if(c.siz[x] < sizy) nsiz += c.siz[x], nhx += F(c.f[x]);
            else    break;
        if(nsiz != sizy) {
            if(i < c.edge[tmp].size())  sizx += c.siz[c.edge[tmp][i]], hx += F(c.f[c.edge[tmp][i]]);
            continue;
        }
        b.Dfs(1, nhx);
        if(a.g[1] + b.g[1] == c.f[1] + 1)   return output(tmp, sizx, rt, sizy), 1;
        if(i < c.edge[tmp].size())  sizx += c.siz[c.edge[tmp][i]], hx += F(c.f[c.edge[tmp][i]]);
    }
    return 0;
}
int solve2() {
    int tmp = c.edge[1].back(), sizx = 1;   ull hx = 1;
    for(int i = 0; i <= c.edge[tmp].size(); ++i) {
        if(i < c.edge[tmp].size() && c.siz[c.edge[tmp][i]] % sizx) {
            if(i < c.edge[tmp].size())  sizx += c.siz[c.edge[tmp][i]], hx += F(c.f[c.edge[tmp][i]]);
            continue;
        }
        int sizy = max(0ll, (c.n + 1 - 1ll * b.n * sizx) / a.n), rt = 0;
        if(1ll * b.n * sizx + 1ll * a.n * sizy - 1 != c.n || !sizy) {
            if(i < c.edge[tmp].size())  sizx += c.siz[c.edge[tmp][i]], hx += F(c.f[c.edge[tmp][i]]);
            continue;
        }
        multiset<ull> nw;   
        b.Dfs(1, hx);
        for(int x : b.edge[1])  nw.insert(b.g[x]);
        for(int j = 0; j < i; ++j)  nw.insert(c.f[c.edge[tmp][j]]);
        for(int j = (int)c.edge[1].size() - 1; j >= 0; --j) {
            int x = c.edge[1][j];
            if(nw.empty() || nw.find(c.f[x]) == nw.end())   {rt = x;    break;}
            nw.erase(nw.find(c.f[x]));
        }
        if(!rt || rt == tmp || c.siz[rt] % sizy) {
            if(i < c.edge[tmp].size())  sizx += c.siz[c.edge[tmp][i]], hx += F(c.f[c.edge[tmp][i]]);
            continue;
        }
        int nsiz = 1;   ull nhx = 1;
        for(int x : c.edge[rt])
            if(c.siz[x] < sizy) nsiz += c.siz[x], nhx += F(c.f[x]);
            else    break;
        if(nsiz != sizy) {
            if(i < c.edge[tmp].size())  sizx += c.siz[c.edge[tmp][i]], hx += F(c.f[c.edge[tmp][i]]);
            continue;
        }
        a.Dfs(1, nhx);
        if(a.g[1] + b.g[1] == c.f[1] + 1)   return output(tmp, sizx, rt, sizy), 1;
        if(i < c.edge[tmp].size())  sizx += c.siz[c.edge[tmp][i]], hx += F(c.f[c.edge[tmp][i]]);
    }
    return 0;
}
void mian() {
    read(a.n, b.n, c.n);
    a.input(), b.input(), c.input();
    a.work(), b.work(), c.work(), flag = 0;
    if(solve()) return;
    flag = 1;
    if(!solve2())    puts("Impossible");
}
int main() {
    #ifdef Kelly
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        freopen("err.txt", "w", stderr);
    #endif
    int T = 1;  read(T);
    while(T--)  mian();
    return 0;
}

Source code, Language: C++17

这程序好像有点Bug，我给组数据试试？

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 18316kb

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: 80ms

memory: 30996kb

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:

3 1
0 1 1 
0 
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 1 1 4 
1 1
0 
0 
8 2
0 1 1 1 1 5 5 5 
0 1 
1 1
0 
0 
4 1
0 1 1 1 
0 
3 1
0 1 1 
0 
5 1
0 1 1 1 4 
0 
1 1
0 
0 
1 1
0 
0 
1 1
0 
0 
1 1
0 
0 
2 1
0 1 
0 
5 1
0 1 1 1 1 
0 
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: 2ms

memory: 19408kb

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 1 3 3

result:

ok 1 cases passed

Extra Test:

score: 0

Extra Test Passed