QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#722977#9459. Tree EquationSkyMathsAC ✓96ms16588kbC++203.5kb2024-11-07 20:47:032024-11-07 20:47:04

Judging History

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

  • [2024-11-07 20:47:04]
  • 评测
  • 测评结果:AC
  • 用时:96ms
  • 内存:16588kb
  • [2024-11-07 20:47:03]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i,l,r) for (int i(l), i##end(r); i <= i##end; ++i)
#define per(i,r,l) for (int i(r), i##end(l); i >= i##end; --i)
#define ll long long
#define ull unsigned long long
#define fi first
#define se second
#define uint unsigned int
#define eb emplace_back
#define File(filename) freopen(filename".in", "r", stdin), freopen(filename".out", "w", stdout)
using namespace std;
template <typename Tx> inline void read(Tx &x) {x = 0; bool f = 0; char ch = getchar(); while (ch < '0' || ch > '9') f ^= ch == '-', ch = getchar(); while (ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar(); if (f) x = -x;}
template <typename Tx, typename ...Ty> inline void read(Tx &x, Ty &...y) {read(x); read(y...);}
template <typename Tx> inline void owrite(Tx x) {if (x > 9) owrite(x / 10); putchar('0' + x % 10);}
template <typename Tx> inline void write(Tx x, char ch = '\n') {owrite(x < 0 ? (putchar('-'), -x) : x); putchar(ch);}
template <typename Tx> inline void cmax(Tx &x, Tx y) {if (x < y) x = y;}
template <typename Tx> inline void cmin(Tx &x, Tx y) {if (x > y) x = y;}
namespace Main {

const int N = 1e5 + 9;
mt19937 mtrnd(time(NULL));
ull mask;
ull shift(ull x) { return x ^= mask, x ^= x << 13, x ^= x >> 7, x ^= x << 17, x ^= mask, x;}

struct Tree {
    vector <int> G[N];
    int dep[N], siz[N];
    ull hsh[N];
    void dfs(int u) {
        siz[u] = hsh[u] = 1;
        for (int v : G[u]) {
            dep[v] = dep[u] + 1;
            dfs(v);
            siz[u] += siz[v];
            hsh[u] += shift(hsh[v]);
        }
    }
    ull calc(int u, ull x) {
        ull ans = x;
        for (int v : G[u]) ans += shift(calc(v, x));
        return ans;
    }
    void init(int n) {
        rep (i, 1, n) vector <int> ().swap(G[i]);
        rep (i, 1, n) {
            int fa; read(fa);
            G[fa].eb(i);
        }
        dfs(1);
    }
    void output(int u, int fa, int &tot) {
        int id = ++tot;
        write(fa, ' ');
        for (int v : G[u]) output(v, id, tot);
    }
} A, B, C;

int a, b, n;

void skymaths() {
    mask = mtrnd() * mtrnd();
    read(a, b, n);
    A.init(a), B.init(b), C.init(n);
    int mxa(0), mxb(0);
    rep (i, 1, a) cmax(mxa, A.dep[i]);
    rep (i, 1, b) cmax(mxb, B.dep[i]);

    map <ull, int> visx, visy, rtx, rty;

    // X, Y 肯定在 C 中出现过
    rep (i, 1, n) {
        if (a <= n / C.siz[i] && !visx[C.hsh[i]]) {
            visx[C.hsh[i]] = 1;
            rtx[A.calc(1, C.hsh[i])] = i;
        }
    }
    rep (i, 1, n) {
        if (b <= n / C.siz[i] && !visy[C.hsh[i]]) {
            visy[C.hsh[i]] = 1;
            rty[B.calc(1, C.hsh[i])] = i;
        }
    }
    int flag = 0;
    for (auto pr : rtx) {
        // 判定当 X = subtree(C[pr.se]) 时可不可以
        // 此时 hsh(A · X) = pr.fi
        ull val = pr.fi, val_by = C.hsh[1] + 1 - val;
        if (rty.count(val_by)) {
            int rx = pr.se, ry = rty[val_by];
            write(C.siz[rx], ' ');
            write(C.siz[ry], '\n');
            int tot1(0), tot2(0);
            C.output(rx, 0, tot1); putchar('\n');
            C.output(ry, 0, tot2); putchar('\n');
            flag = 1; break;
        }
    }
    if (!flag) {
        printf("Impossible\n");
    }
}

/*
code from Purslane
thx
*/

signed main() {
    // freopen("a.in", "r", stdin);
    int T = 1;
    read(T);
    while (T--) {
        skymaths();
    }
    return 0;
} } signed main() { Main::main(); return 0;}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 15400kb

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: 96ms
memory: 16588kb

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 2 1 1 
1 1
0 
0 
2 8
0 1 
0 1 1 3 3 3 1 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 
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: 3ms
memory: 14304kb

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