oj.uz

답안 #471860

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
471860 2021-09-11T09:21:27 Z shrimb Mergers (JOI19_mergers) C++17
0 / 100
 226 ms 109416 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 = n;
    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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 94148 KB Output is correct
2 Correct 64 ms 94172 KB Output is correct
3 Correct 64 ms 94244 KB Output is correct
4 Correct 65 ms 94212 KB Output is correct
5 Correct 63 ms 94156 KB Output is correct
6 Correct 63 ms 94236 KB Output is correct
7 Correct 64 ms 94236 KB Output is correct
8 Correct 63 ms 94308 KB Output is correct
9 Correct 63 ms 94220 KB Output is correct
10 Correct 65 ms 94204 KB Output is correct
11 Correct 64 ms 94196 KB Output is correct
12 Incorrect 64 ms 94148 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 94148 KB Output is correct
2 Correct 64 ms 94172 KB Output is correct
3 Correct 64 ms 94244 KB Output is correct
4 Correct 65 ms 94212 KB Output is correct
5 Correct 63 ms 94156 KB Output is correct
6 Correct 63 ms 94236 KB Output is correct
7 Correct 64 ms 94236 KB Output is correct
8 Correct 63 ms 94308 KB Output is correct
9 Correct 63 ms 94220 KB Output is correct
10 Correct 65 ms 94204 KB Output is correct
11 Correct 64 ms 94196 KB Output is correct
12 Incorrect 64 ms 94148 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 94148 KB Output is correct
2 Correct 64 ms 94172 KB Output is correct
3 Correct 64 ms 94244 KB Output is correct
4 Correct 65 ms 94212 KB Output is correct
5 Correct 63 ms 94156 KB Output is correct
6 Correct 63 ms 94236 KB Output is correct
7 Correct 64 ms 94236 KB Output is correct
8 Correct 63 ms 94308 KB Output is correct
9 Correct 63 ms 94220 KB Output is correct
10 Correct 65 ms 94204 KB Output is correct
11 Correct 64 ms 94196 KB Output is correct
12 Incorrect 64 ms 94148 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 147 ms 107564 KB Output is correct
2 Correct 226 ms 109416 KB Output is correct
3 Incorrect 68 ms 94660 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 94148 KB Output is correct
2 Correct 64 ms 94172 KB Output is correct
3 Correct 64 ms 94244 KB Output is correct
4 Correct 65 ms 94212 KB Output is correct
5 Correct 63 ms 94156 KB Output is correct
6 Correct 63 ms 94236 KB Output is correct
7 Correct 64 ms 94236 KB Output is correct
8 Correct 63 ms 94308 KB Output is correct
9 Correct 63 ms 94220 KB Output is correct
10 Correct 65 ms 94204 KB Output is correct
11 Correct 64 ms 94196 KB Output is correct
12 Incorrect 64 ms 94148 KB Output isn't correct
13 Halted 0 ms 0 KB -