oj.uz

Submission #1044320

# Submission time Handle Problem Language Result Execution time Memory
1044320 2024-08-05T08:50:39 Z 변재우(#11009) Team Coding (EGOI24_teamcoding) C++17
50 / 100
 4000 ms 106436 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int Nmax=100010;
int N, K, ans, mn, A[Nmax], C[Nmax], D[Nmax];
vector<int> adj[Nmax];
unordered_map<int, int> X[Nmax];

void DFS1(int curr) {
    X[A[curr]][D[curr]]++;
    for(int next:adj[curr]) D[next]=D[curr]+1, DFS1(next);
}

pair<unordered_map<int, int>, unordered_map<int, unordered_map<int, int>>> DFS(int curr) {
    pair<unordered_map<int, int>, unordered_map<int, unordered_map<int, int>>> ret;
    ret.first[D[curr]]++, ret.second[A[curr]][D[curr]]++;
    for(int next:adj[curr]) {
        pair<unordered_map<int, int>, unordered_map<int, unordered_map<int, int>>> tmp=DFS(next);
        if(ret.first.size()<tmp.first.size()) swap(ret, tmp);
        for(auto k:tmp.first) ret.first[k.first]+=k.second;
        for(auto k:tmp.second) for(auto kk:k.second) ret.second[k.first][kk.first]+=kk.second;
    }
    int sum=0, val=0;
    for(auto k:X[A[curr]]) sum+=min(X[A[curr]][k.first], ret.first[k.first]), val+=ret.second[A[curr]][k.first];
    val=sum-val;
    if(ans<sum) ans=sum, mn=val;
    if(ans==sum && mn>val) mn=val;
    return ret;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>K;
    for(int i=1; i<=N; i++) cin>>A[i], C[++A[i]]++;
    for(int i=2; i<=N; i++) {
        int p; cin>>p; adj[++p].push_back(i);
    }
    DFS1(1);
    DFS(1);
    cout<<ans<<" "<<mn;
    return 0;
}

Subtask #1
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8800 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 6 ms 10588 KB Output is correct
9 Correct 258 ms 104336 KB Output is correct
10 Correct 2 ms 8796 KB Output is correct
11 Correct 55 ms 10588 KB Output is correct
12 Execution timed out 4059 ms 106008 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #2
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 42 ms 10588 KB Output is correct
5 Execution timed out 4043 ms 106200 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8792 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 1 ms 8856 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8860 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 222 ms 104216 KB Output is correct
9 Correct 2 ms 8792 KB Output is correct
10 Correct 4 ms 10584 KB Output is correct
11 Correct 223 ms 106436 KB Output is correct
12 Correct 3 ms 8792 KB Output is correct
13 Correct 2 ms 8796 KB Output is correct
14 Correct 2 ms 8796 KB Output is correct
15 Correct 6 ms 9304 KB Output is correct
16 Correct 7 ms 9304 KB Output is correct
17 Correct 3 ms 9308 KB Output is correct
18 Correct 414 ms 40916 KB Output is correct
19 Correct 323 ms 39244 KB Output is correct
20 Correct 445 ms 62636 KB Output is correct
21 Correct 184 ms 22684 KB Output is correct
22 Correct 238 ms 41912 KB Output is correct
23 Correct 270 ms 77220 KB Output is correct
24 Correct 190 ms 55744 KB Output is correct
25 Correct 4 ms 9720 KB Output is correct
26 Correct 4 ms 10364 KB Output is correct
27 Correct 5 ms 9308 KB Output is correct
28 Correct 5 ms 9308 KB Output is correct
29 Correct 22 ms 12444 KB Output is correct
30 Correct 420 ms 40620 KB Output is correct
31 Correct 326 ms 48716 KB Output is correct
32 Correct 311 ms 55472 KB Output is correct
33 Correct 198 ms 36352 KB Output is correct
34 Correct 2 ms 8796 KB Output is correct
35 Correct 2 ms 8796 KB Output is correct
36 Correct 2 ms 8796 KB Output is correct
37 Correct 1 ms 8796 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 9048 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 8 ms 10588 KB Output is correct
9 Correct 2 ms 8796 KB Output is correct
10 Correct 39 ms 10748 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 4 ms 10588 KB Output is correct
13 Correct 2 ms 8796 KB Output is correct
14 Correct 3 ms 8912 KB Output is correct
15 Correct 2 ms 8796 KB Output is correct
16 Correct 175 ms 51504 KB Output is correct
17 Correct 2 ms 8796 KB Output is correct
18 Correct 2 ms 8796 KB Output is correct
19 Correct 2 ms 8796 KB Output is correct
20 Correct 5 ms 8796 KB Output is correct
21 Correct 2 ms 8796 KB Output is correct
22 Correct 3 ms 8796 KB Output is correct
23 Correct 5 ms 9460 KB Output is correct
24 Correct 6 ms 9444 KB Output is correct
25 Correct 4 ms 9308 KB Output is correct
26 Correct 5 ms 9668 KB Output is correct
27 Correct 6 ms 10248 KB Output is correct
28 Correct 6 ms 9308 KB Output is correct
29 Correct 5 ms 9308 KB Output is correct
30 Correct 236 ms 48976 KB Output is correct
31 Correct 9 ms 9052 KB Output is correct
32 Correct 4 ms 8800 KB Output is correct
33 Correct 4 ms 9312 KB Output is correct
34 Correct 4 ms 8792 KB Output is correct
35 Correct 3 ms 8800 KB Output is correct
36 Correct 3 ms 8808 KB Output is correct
37 Correct 4 ms 8800 KB Output is correct
38 Correct 2 ms 8800 KB Output is correct
39 Correct 2 ms 8800 KB Output is correct
40 Correct 2 ms 8792 KB Output is correct
41 Correct 2 ms 8796 KB Output is correct

Subtask #5
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8800 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 6 ms 10588 KB Output is correct
9 Correct 258 ms 104336 KB Output is correct
10 Correct 2 ms 8796 KB Output is correct
11 Correct 55 ms 10588 KB Output is correct
12 Execution timed out 4059 ms 106008 KB Time limit exceeded
13 Halted 0 ms 0 KB -