QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#609752#5454. Subtree ActivationDimash#66.666667 651ms39876kbC++233.2kb2024-10-04 13:53:362024-10-04 13:53:37

Judging History

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

  • [2024-10-04 13:53:37]
  • 评测
  • 测评结果:66.666667
  • 用时:651ms
  • 内存:39876kb
  • [2024-10-04 13:53:36]
  • 提交

answer

#include <bits/stdc++.h>
    
using namespace std;
    
typedef long long ll;
const int  N = 1e6 + 12, MOD = (int)1e9 + 7;


int n, tin[N], tout[N], timer = 0, s[N], P[N], pp[N], dep[N];

ll res = 0;
vector<int> g[N];
void dfs(int v) {
    tin[v] = ++timer;
    s[v] = 1;
    for(int to:g[v]) {
        dfs(to);
        dep[to] = dep[v] + 1;
        s[v] += s[to];
    }
    res += s[v] * 2ll;
    tout[v] = ++timer;
}
bool is(int v, int u) {
    return (tin[v] <= tin[u] && tout[u] <= tout[v]);
}
ll calc(deque<int> &p) {
    ll x = 0;
    for(int i = 1; i < n; i++) {
        if(is(p[i], p[i - 1])) {
            x += 2 * s[p[i - 1]];
        } else if(is(p[i - 1], p[i])) {
            x += 2 * s[p[i]];
        }
    }
    return x;
}
bool ii = 1;
int l[N], r[N];
bool cmp(int x, int y) {
    if(s[x] == s[y]) {
        return dep[x] > dep[y];
    }
    return s[x] > s[y];
}
int get(int v) {
    if(pp[v] == v) return v;
    return pp[v] = get(pp[v]);
}
void merge(int a, int b) {
    a = get(a);
    b = get(b);
    pp[b] = a;
}
void test() {
    cin >> n;
    for(int i = 2; i <= n; i++) {
        int p;
        cin >> p;
        P[i] = p;
        g[p].push_back(i);
    }
    for(int i = 1; i <= n; i++) {
        pp[i] = i;
    }
    dfs(1);
    memset(l, -1, sizeof(l));
    memset(r, -1, sizeof(r));
    vector<int> p(n);
    iota(p.begin(), p.end(), 1);
    sort(p.begin(), p.end(), cmp);
    for(int i:p) {
        int v = P[i];
        while(v) {
            if(l[v] == -1 && r[i] == -1) {
                l[v] = i;
                r[i] = v;
                merge(v, i);
                break;
            }
            else if(r[v] == -1 && l[i] == -1) {
                r[v] = i;
                l[i] = v;
                merge(v, i);
                break;
            }
            v = get(P[v]);
        }
        v = P[i];
        while(v) {
            if(get(v) == get(i)) {
                v = P[v];
                continue;
            }
            if(l[v] == -1 && l[i] != v && r[i] != v && r[i] == -1) {
                l[v] = i;
                r[i] = v;
                merge(v, i);
                break;
            }
            else if(r[v] == -1 && l[i] != v && r[i] != v && l[i] == -1) {
                r[v] = i;
                l[i] = v;
                merge(v, i);
                break;
            }
            v = get(P[v]);
        }
    }
    ll x = 0;
    // vector<int> o;
    for(int i = 1; i <= n; i++) {
        // if(l[i] == -1) {
        //     int x = i;
        //     while(x != -1) {
        //         cout << x << ' ';
        //         x = r[x];
        //     }
        //     cout << '\n';
        // }
        // cout << i << ' ' << l[i] << ' ' << r[i] << '\n';
        if(r[i] != -1) {
            if(is(r[i], i)) {
                x += 2 * s[i];
            } else if(is(i, r[i])) {
                x += 2 * s[r[i]];
            }
        }
    }
    cout << res - x << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); 
    
    int t = 1; 
    // cin >> t;
    
    while(t--) 
        test();
    return 0;
}

詳細信息


Pretests


Final Tests

Test #1:

score: 4.7619
Accepted
time: 0ms
memory: 21584kb

input:

3
1 1

output:

6

result:

ok 1 number(s): "6"

Test #2:

score: 4.7619
Accepted
time: 0ms
memory: 21644kb

input:

8
1 2 1 1 5 3 4

output:

20

result:

ok 1 number(s): "20"

Test #3:

score: 4.7619
Accepted
time: 4ms
memory: 21588kb

input:

8
1 2 1 4 5 4 4

output:

20

result:

ok 1 number(s): "20"

Test #4:

score: 4.7619
Accepted
time: 4ms
memory: 21588kb

input:

40
1 1 1 1 1 1 1 1 1 7 11 10 12 13 15 16 16 15 18 20 21 21 21 21 21 21 21 21 21 6 18 28 12 34 22 6 15 23 32

output:

130

result:

ok 1 number(s): "130"

Test #5:

score: 4.7619
Accepted
time: 0ms
memory: 21808kb

input:

40
1 1 1 1 1 1 1 1 1 10 9 12 8 14 15 16 17 12 17 19 21 21 21 21 21 21 21 21 21 23 26 15 9 6 27 32 5 11 8

output:

132

result:

ok 1 number(s): "132"

Test #6:

score: 4.7619
Accepted
time: 5ms
memory: 21652kb

input:

40
1 1 1 1 1 1 1 1 1 6 11 12 13 8 15 15 16 18 17 18 21 21 21 21 21 21 21 21 21 23 13 17 8 20 6 24 27 38 36

output:

132

result:

ok 1 number(s): "132"

Test #7:

score: 4.7619
Accepted
time: 0ms
memory: 21680kb

input:

40
1 1 1 1 1 1 1 1 1 10 11 7 13 14 15 16 17 18 18 18 21 21 21 21 21 21 21 21 21 25 11 13 13 3 24 11 25 35 28

output:

132

result:

ok 1 number(s): "132"

Test #8:

score: 4.7619
Accepted
time: 4ms
memory: 21612kb

input:

40
1 1 1 1 1 1 1 1 1 10 11 12 11 14 14 14 17 16 16 20 21 21 21 21 21 21 21 21 21 17 22 25 14 25 29 23 1 17 14

output:

138

result:

ok 1 number(s): "138"

Test #9:

score: 4.7619
Accepted
time: 0ms
memory: 21888kb

input:

40
1 1 1 1 1 1 1 1 1 7 11 12 12 13 14 13 16 18 19 20 21 21 21 21 21 21 21 21 21 17 8 17 33 27 3 34 20 4 10

output:

126

result:

ok 1 number(s): "126"

Test #10:

score: 4.7619
Accepted
time: 0ms
memory: 21848kb

input:

5000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

18824

result:

ok 1 number(s): "18824"

Test #11:

score: 4.7619
Accepted
time: 3ms
memory: 21904kb

input:

5000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

18914

result:

ok 1 number(s): "18914"

Test #12:

score: 4.7619
Accepted
time: 3ms
memory: 23896kb

input:

5000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

18854

result:

ok 1 number(s): "18854"

Test #13:

score: 0
Wrong Answer
time: 0ms
memory: 22104kb

input:

5000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

18898

result:

wrong answer 1st numbers differ - expected: '18894', found: '18898'

Test #14:

score: 4.7619
Accepted
time: 0ms
memory: 21844kb

input:

5000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

18956

result:

ok 1 number(s): "18956"

Test #15:

score: 4.7619
Accepted
time: 3ms
memory: 21848kb

input:

5000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

18882

result:

ok 1 number(s): "18882"

Test #16:

score: 0
Wrong Answer
time: 630ms
memory: 31576kb

input:

200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

756562

result:

wrong answer 1st numbers differ - expected: '756550', found: '756562'

Test #17:

score: 0
Wrong Answer
time: 647ms
memory: 33708kb

input:

200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

755662

result:

wrong answer 1st numbers differ - expected: '755654', found: '755662'

Test #18:

score: 0
Wrong Answer
time: 651ms
memory: 35036kb

input:

200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

755836

result:

wrong answer 1st numbers differ - expected: '755830', found: '755836'

Test #19:

score: 0
Wrong Answer
time: 641ms
memory: 31560kb

input:

200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

756828

result:

wrong answer 1st numbers differ - expected: '756822', found: '756828'

Test #20:

score: 0
Wrong Answer
time: 636ms
memory: 39876kb

input:

200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

756218

result:

wrong answer 1st numbers differ - expected: '756212', found: '756218'

Test #21:

score: 0
Wrong Answer
time: 645ms
memory: 31616kb

input:

200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

755934

result:

wrong answer 1st numbers differ - expected: '755930', found: '755934'