oj.uz

Submission #446423

# Submission time Handle Problem Language Result Execution time Memory
446423 2021-07-21T21:52:53 Z MladenP Capital City (JOI20_capital_city) C++17
11 / 100
 3000 ms 39576 KB 
#include <bits/stdc++.h>
#define PRINT(x) cerr<<#x<<'='<<x<<endl;
#define NL(x) " \n"[(x)]
#define lld long long
#define pil pair<int,lld>
#define pli pair<lld,int>
#define pll pair<lld,lld>
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#define mid (l+r)/2
#define endl '\n'
#define all(a) begin(a),end(a)
#define sz(a) int((a).size())
#define LINF 1000000000000000LL
#define INF 1000000000
#define EPS 1e-9
using namespace std;
#define MAXN 200010
int N, K, C[MAXN], siz[MAXN], par[MAXN], sol;
bool vis[MAXN], col[MAXN], pos[MAXN], ovde[MAXN];
vector<int> adj[MAXN], v, pC[MAXN];
int dfsSize(int node, int prev) {
    siz[node] = 1;
    for(auto x : adj[node]) {
        if(!vis[x] && x != prev) siz[node] += dfsSize(x, node);
    }
    return siz[node];
}
int dfsCent(int node, int prev, int S) {
    for(auto x : adj[node]) {
        if(!vis[x] && x != prev && siz[x] > S/2) return dfsCent(x, node, S);
    }
    return node;
}
void dfsParent(int node, int prev) {
    par[node] = prev;
    ovde[node] = true;
    v.pb(node);
    for(auto x : adj[node]) {
        if(x != prev) dfsParent(x, node);
    }
}
vector<int> nv;
int boja = 0;
bool addColor(int color) {
    if(col[color]) return true;
    boja++;
    col[color] = true;
    for(auto x : pC[color]) {
        if(!ovde[x]) return false;
        if(!pos[x]) nv.pb(x);
    }
    return true;
}
void centDecomp(int node) {
    int S = dfsSize(node, node);
    node = dfsCent(node, node, S);
    vis[node] = 1;
    dfsParent(node, node);
    boja = 0;
    if(!addColor(C[node])) nv.clear();
    while(!nv.empty()) {
        int cur = nv.back(); nv.pop_back();
        while(1) {
            pos[cur] = true;
            if(!addColor(C[cur])) {
                nv.clear();
                break;
            }
            if(par[cur] == cur || pos[par[cur]]) break;
            cur = par[cur];
        }
    }
    sol = min(sol, boja);
    for(auto x : v) pos[x] = ovde[x] = col[C[x]] = 0;
    v.clear();
    for(auto x : adj[node]) if(!vis[x]) centDecomp(x);
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> N >> K;
    for(int i = 1; i <= N-1; i++) {
        int x, y; cin >> x >> y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    for(int i = 1; i <= N; i++) {
        cin >> C[i];
        pC[C[i]].pb(i);
    }
    sol = K;
    centDecomp(1);
    cout << sol-1;
    return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9716 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 6 ms 9720 KB Output is correct
7 Correct 6 ms 9708 KB Output is correct
8 Correct 6 ms 9716 KB Output is correct
9 Correct 6 ms 9712 KB Output is correct
10 Correct 7 ms 9632 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9716 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 6 ms 9720 KB Output is correct
7 Correct 6 ms 9708 KB Output is correct
8 Correct 6 ms 9716 KB Output is correct
9 Correct 6 ms 9712 KB Output is correct
10 Correct 7 ms 9632 KB Output is correct
11 Correct 164 ms 9804 KB Output is correct
12 Correct 166 ms 9804 KB Output is correct
13 Correct 172 ms 9880 KB Output is correct
14 Correct 167 ms 9856 KB Output is correct
15 Correct 87 ms 9932 KB Output is correct
16 Correct 103 ms 9804 KB Output is correct
17 Correct 106 ms 9932 KB Output is correct
18 Correct 105 ms 9932 KB Output is correct
19 Correct 104 ms 9944 KB Output is correct
20 Correct 104 ms 9932 KB Output is correct
21 Correct 105 ms 9952 KB Output is correct
22 Correct 102 ms 10028 KB Output is correct
23 Correct 131 ms 9984 KB Output is correct
24 Correct 98 ms 9932 KB Output is correct
25 Correct 143 ms 9976 KB Output is correct
26 Correct 147 ms 10008 KB Output is correct
27 Correct 144 ms 9932 KB Output is correct
28 Correct 121 ms 9968 KB Output is correct
29 Correct 124 ms 9964 KB Output is correct
30 Correct 123 ms 9932 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3095 ms 39576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9716 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 6 ms 9720 KB Output is correct
7 Correct 6 ms 9708 KB Output is correct
8 Correct 6 ms 9716 KB Output is correct
9 Correct 6 ms 9712 KB Output is correct
10 Correct 7 ms 9632 KB Output is correct
11 Correct 164 ms 9804 KB Output is correct
12 Correct 166 ms 9804 KB Output is correct
13 Correct 172 ms 9880 KB Output is correct
14 Correct 167 ms 9856 KB Output is correct
15 Correct 87 ms 9932 KB Output is correct
16 Correct 103 ms 9804 KB Output is correct
17 Correct 106 ms 9932 KB Output is correct
18 Correct 105 ms 9932 KB Output is correct
19 Correct 104 ms 9944 KB Output is correct
20 Correct 104 ms 9932 KB Output is correct
21 Correct 105 ms 9952 KB Output is correct
22 Correct 102 ms 10028 KB Output is correct
23 Correct 131 ms 9984 KB Output is correct
24 Correct 98 ms 9932 KB Output is correct
25 Correct 143 ms 9976 KB Output is correct
26 Correct 147 ms 10008 KB Output is correct
27 Correct 144 ms 9932 KB Output is correct
28 Correct 121 ms 9968 KB Output is correct
29 Correct 124 ms 9964 KB Output is correct
30 Correct 123 ms 9932 KB Output is correct
31 Execution timed out 3095 ms 39576 KB Time limit exceeded
32 Halted 0 ms 0 KB -