oj.uz

Submission #471861

# Submission time Handle Problem Language Result Execution time Memory
471861 2021-09-11T09:23:33 Z shrimb Mergers (JOI19_mergers) C++17
10 / 100
 200 ms 107596 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 ROOT;
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 != ROOT) {
        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 == ROOT) {
                cunt += min(ret, x);
                // cerr << cunt << endl;
                ret = abs(ret - x);
            }
            else ret += x;
        }
    }
    if (ret == 0 and cur != ROOT) 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;
    ROOT = rand() % n + 1;
    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(ROOT, 0);
    // for (int i = 1 ; i <= n ; i++) cout << bad[i] << " "; cout << endl;
    int x = calc_ans(ROOT, 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 65 ms 94148 KB Output is correct
2 Correct 63 ms 94156 KB Output is correct
3 Correct 64 ms 94228 KB Output is correct
4 Correct 62 ms 94140 KB Output is correct
5 Correct 64 ms 94148 KB Output is correct
6 Correct 65 ms 94200 KB Output is correct
7 Correct 63 ms 94148 KB Output is correct
8 Correct 65 ms 94180 KB Output is correct
9 Correct 66 ms 94256 KB Output is correct
10 Correct 64 ms 94260 KB Output is correct
11 Correct 63 ms 94164 KB Output is correct
12 Correct 63 ms 94268 KB Output is correct
13 Correct 64 ms 94148 KB Output is correct
14 Correct 64 ms 94208 KB Output is correct
15 Correct 64 ms 94260 KB Output is correct
16 Correct 66 ms 94152 KB Output is correct
17 Correct 65 ms 94164 KB Output is correct
18 Correct 69 ms 94276 KB Output is correct
19 Correct 66 ms 94148 KB Output is correct
20 Correct 65 ms 94256 KB Output is correct
21 Correct 63 ms 94216 KB Output is correct
22 Correct 64 ms 94252 KB Output is correct
23 Correct 66 ms 94176 KB Output is correct
24 Correct 65 ms 94148 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 94148 KB Output is correct
2 Correct 63 ms 94156 KB Output is correct
3 Correct 64 ms 94228 KB Output is correct
4 Correct 62 ms 94140 KB Output is correct
5 Correct 64 ms 94148 KB Output is correct
6 Correct 65 ms 94200 KB Output is correct
7 Correct 63 ms 94148 KB Output is correct
8 Correct 65 ms 94180 KB Output is correct
9 Correct 66 ms 94256 KB Output is correct
10 Correct 64 ms 94260 KB Output is correct
11 Correct 63 ms 94164 KB Output is correct
12 Correct 63 ms 94268 KB Output is correct
13 Correct 64 ms 94148 KB Output is correct
14 Correct 64 ms 94208 KB Output is correct
15 Correct 64 ms 94260 KB Output is correct
16 Correct 66 ms 94152 KB Output is correct
17 Correct 65 ms 94164 KB Output is correct
18 Correct 69 ms 94276 KB Output is correct
19 Correct 66 ms 94148 KB Output is correct
20 Correct 65 ms 94256 KB Output is correct
21 Correct 63 ms 94216 KB Output is correct
22 Correct 64 ms 94252 KB Output is correct
23 Correct 66 ms 94176 KB Output is correct
24 Correct 65 ms 94148 KB Output is correct
25 Correct 63 ms 94240 KB Output is correct
26 Incorrect 69 ms 94652 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 94148 KB Output is correct
2 Correct 63 ms 94156 KB Output is correct
3 Correct 64 ms 94228 KB Output is correct
4 Correct 62 ms 94140 KB Output is correct
5 Correct 64 ms 94148 KB Output is correct
6 Correct 65 ms 94200 KB Output is correct
7 Correct 63 ms 94148 KB Output is correct
8 Correct 65 ms 94180 KB Output is correct
9 Correct 66 ms 94256 KB Output is correct
10 Correct 64 ms 94260 KB Output is correct
11 Correct 63 ms 94164 KB Output is correct
12 Correct 63 ms 94268 KB Output is correct
13 Correct 64 ms 94148 KB Output is correct
14 Correct 64 ms 94208 KB Output is correct
15 Correct 64 ms 94260 KB Output is correct
16 Correct 66 ms 94152 KB Output is correct
17 Correct 65 ms 94164 KB Output is correct
18 Correct 69 ms 94276 KB Output is correct
19 Correct 66 ms 94148 KB Output is correct
20 Correct 65 ms 94256 KB Output is correct
21 Correct 63 ms 94216 KB Output is correct
22 Correct 64 ms 94252 KB Output is correct
23 Correct 66 ms 94176 KB Output is correct
24 Correct 65 ms 94148 KB Output is correct
25 Correct 65 ms 94212 KB Output is correct
26 Correct 151 ms 107596 KB Output is correct
27 Correct 200 ms 102124 KB Output is correct
28 Incorrect 65 ms 94404 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 106108 KB Output is correct
2 Correct 197 ms 107576 KB Output is correct
3 Incorrect 70 ms 94532 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 94148 KB Output is correct
2 Correct 63 ms 94156 KB Output is correct
3 Correct 64 ms 94228 KB Output is correct
4 Correct 62 ms 94140 KB Output is correct
5 Correct 64 ms 94148 KB Output is correct
6 Correct 65 ms 94200 KB Output is correct
7 Correct 63 ms 94148 KB Output is correct
8 Correct 65 ms 94180 KB Output is correct
9 Correct 66 ms 94256 KB Output is correct
10 Correct 64 ms 94260 KB Output is correct
11 Correct 63 ms 94164 KB Output is correct
12 Correct 63 ms 94268 KB Output is correct
13 Correct 64 ms 94148 KB Output is correct
14 Correct 64 ms 94208 KB Output is correct
15 Correct 64 ms 94260 KB Output is correct
16 Correct 66 ms 94152 KB Output is correct
17 Correct 65 ms 94164 KB Output is correct
18 Correct 69 ms 94276 KB Output is correct
19 Correct 66 ms 94148 KB Output is correct
20 Correct 65 ms 94256 KB Output is correct
21 Correct 63 ms 94216 KB Output is correct
22 Correct 64 ms 94252 KB Output is correct
23 Correct 66 ms 94176 KB Output is correct
24 Correct 65 ms 94148 KB Output is correct
25 Correct 63 ms 94240 KB Output is correct
26 Incorrect 69 ms 94652 KB Output isn't correct
27 Halted 0 ms 0 KB -