oj.uz

Submission #471705

# Submission time Handle Problem Language Result Execution time Memory
471705 2021-09-10T12:09:44 Z shrimb Mergers (JOI19_mergers) C++17
10 / 100
 201 ms 107608 KB 
#include"bits/stdc++.h"
#define int long long
#define endl '\n'
#define USACO(x) ifstream cin ((string)#x + ".in"); ofstream cout((string)#x + ".out")
using namespace std;
const int maxN = 1000001;
int n, k;
vector<int> adj[maxN];
int s[maxN];
int tot[maxN];
int subtree[maxN];

map<int,int>* s2b[maxN];
int cnt[maxN];
bool bad[maxN];

void inc (int a, int b, int v) {
    (*s2b[a])[b] += v;
    if ((*s2b[a])[b] == tot[b]) cnt[a]++;
}

int cunt = 0;

void dfs (int cur, int par) {
    subtree[cur] = 1;
    if (adj[cur].size() == 1 and cur != 1) {
        inc(cur, s[cur], 1);
        bad[cur] = (cnt[cur] == (int)((*s2b[cur]).size()));
        return;
    }
    int best = -1;
    for (int i : adj[cur]) {
        if (i != par) {
            dfs(i, cur);
            subtree[cur] += subtree[i];
            if (best == -1 or subtree[i] > subtree[best]) best = i;
        }
    }

    s2b[cur] = s2b[best];
    cnt[cur] = cnt[best];

    for (int i : adj[cur]) {
        if (i != par and i != best) {
            for (auto j : (*s2b[i])) {
                inc(cur, j.first, j.second);
            }
            (*s2b[i]).clear();
        }
    }

    inc(cur, s[cur], 1);
    bad[cur] = (cnt[cur] == (int)((*s2b[cur]).size()));
}

int calc_ans (int cur, int par) {
    int ret = 0;
    for (int i : adj[cur]) {
        if (i != par) {
            int x = calc_ans(i, cur);
            if (bad[cur] == 0 or cur == 1) {
                cunt += min(ret, x);
                // cerr << cunt << endl;
                ret = abs(ret - x);
            }
            else ret += x;
        }
    }
    if (ret == 0 and cur != 1) ret += bad[cur];
    return ret;
}


signed main() {
    for (auto& i : s2b) i = new map<int,int>();
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;
    if (n ==1) {
        cout << 0 << endl;
        return 0;
    }
    for (int i = 1 ; i < n ; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    for (int i = 1 ; i <= n ; i++) {
        cin >> s[i];
        tot[s[i]]++;
    }
    dfs(1, 0);
    // for (int i = 1 ; i <= n ; i++) cout << bad[i] << " "; cout << endl;
    int x = calc_ans(1, 0);
    cout << cunt + (x ? 1 + ceil((x-1)/2.0) : 0);


}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 94148 KB Output is correct
2 Correct 65 ms 94240 KB Output is correct
3 Correct 66 ms 94204 KB Output is correct
4 Correct 65 ms 94264 KB Output is correct
5 Correct 64 ms 94152 KB Output is correct
6 Correct 64 ms 94212 KB Output is correct
7 Correct 66 ms 94164 KB Output is correct
8 Correct 67 ms 94276 KB Output is correct
9 Correct 65 ms 94148 KB Output is correct
10 Correct 65 ms 94180 KB Output is correct
11 Correct 67 ms 94172 KB Output is correct
12 Correct 65 ms 94200 KB Output is correct
13 Correct 63 ms 94148 KB Output is correct
14 Correct 74 ms 94272 KB Output is correct
15 Correct 74 ms 94268 KB Output is correct
16 Correct 65 ms 94148 KB Output is correct
17 Correct 64 ms 94248 KB Output is correct
18 Correct 68 ms 94240 KB Output is correct
19 Correct 64 ms 94200 KB Output is correct
20 Correct 64 ms 94240 KB Output is correct
21 Correct 72 ms 94164 KB Output is correct
22 Correct 63 ms 94216 KB Output is correct
23 Correct 64 ms 94152 KB Output is correct
24 Correct 63 ms 94156 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 94148 KB Output is correct
2 Correct 65 ms 94240 KB Output is correct
3 Correct 66 ms 94204 KB Output is correct
4 Correct 65 ms 94264 KB Output is correct
5 Correct 64 ms 94152 KB Output is correct
6 Correct 64 ms 94212 KB Output is correct
7 Correct 66 ms 94164 KB Output is correct
8 Correct 67 ms 94276 KB Output is correct
9 Correct 65 ms 94148 KB Output is correct
10 Correct 65 ms 94180 KB Output is correct
11 Correct 67 ms 94172 KB Output is correct
12 Correct 65 ms 94200 KB Output is correct
13 Correct 63 ms 94148 KB Output is correct
14 Correct 74 ms 94272 KB Output is correct
15 Correct 74 ms 94268 KB Output is correct
16 Correct 65 ms 94148 KB Output is correct
17 Correct 64 ms 94248 KB Output is correct
18 Correct 68 ms 94240 KB Output is correct
19 Correct 64 ms 94200 KB Output is correct
20 Correct 64 ms 94240 KB Output is correct
21 Correct 72 ms 94164 KB Output is correct
22 Correct 63 ms 94216 KB Output is correct
23 Correct 64 ms 94152 KB Output is correct
24 Correct 63 ms 94156 KB Output is correct
25 Correct 65 ms 94264 KB Output is correct
26 Incorrect 76 ms 94696 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 94148 KB Output is correct
2 Correct 65 ms 94240 KB Output is correct
3 Correct 66 ms 94204 KB Output is correct
4 Correct 65 ms 94264 KB Output is correct
5 Correct 64 ms 94152 KB Output is correct
6 Correct 64 ms 94212 KB Output is correct
7 Correct 66 ms 94164 KB Output is correct
8 Correct 67 ms 94276 KB Output is correct
9 Correct 65 ms 94148 KB Output is correct
10 Correct 65 ms 94180 KB Output is correct
11 Correct 67 ms 94172 KB Output is correct
12 Correct 65 ms 94200 KB Output is correct
13 Correct 63 ms 94148 KB Output is correct
14 Correct 74 ms 94272 KB Output is correct
15 Correct 74 ms 94268 KB Output is correct
16 Correct 65 ms 94148 KB Output is correct
17 Correct 64 ms 94248 KB Output is correct
18 Correct 68 ms 94240 KB Output is correct
19 Correct 64 ms 94200 KB Output is correct
20 Correct 64 ms 94240 KB Output is correct
21 Correct 72 ms 94164 KB Output is correct
22 Correct 63 ms 94216 KB Output is correct
23 Correct 64 ms 94152 KB Output is correct
24 Correct 63 ms 94156 KB Output is correct
25 Correct 79 ms 94172 KB Output is correct
26 Correct 153 ms 107568 KB Output is correct
27 Correct 180 ms 101944 KB Output is correct
28 Incorrect 83 ms 94492 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 106084 KB Output is correct
2 Correct 201 ms 107608 KB Output is correct
3 Incorrect 72 ms 94516 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 94148 KB Output is correct
2 Correct 65 ms 94240 KB Output is correct
3 Correct 66 ms 94204 KB Output is correct
4 Correct 65 ms 94264 KB Output is correct
5 Correct 64 ms 94152 KB Output is correct
6 Correct 64 ms 94212 KB Output is correct
7 Correct 66 ms 94164 KB Output is correct
8 Correct 67 ms 94276 KB Output is correct
9 Correct 65 ms 94148 KB Output is correct
10 Correct 65 ms 94180 KB Output is correct
11 Correct 67 ms 94172 KB Output is correct
12 Correct 65 ms 94200 KB Output is correct
13 Correct 63 ms 94148 KB Output is correct
14 Correct 74 ms 94272 KB Output is correct
15 Correct 74 ms 94268 KB Output is correct
16 Correct 65 ms 94148 KB Output is correct
17 Correct 64 ms 94248 KB Output is correct
18 Correct 68 ms 94240 KB Output is correct
19 Correct 64 ms 94200 KB Output is correct
20 Correct 64 ms 94240 KB Output is correct
21 Correct 72 ms 94164 KB Output is correct
22 Correct 63 ms 94216 KB Output is correct
23 Correct 64 ms 94152 KB Output is correct
24 Correct 63 ms 94156 KB Output is correct
25 Correct 65 ms 94264 KB Output is correct
26 Incorrect 76 ms 94696 KB Output isn't correct
27 Halted 0 ms 0 KB -