oj.uz

Submission #446424

# Submission time Handle Problem Language Result Execution time Memory
446424 2021-07-21T21:57:37 Z MladenP Capital City (JOI20_capital_city) C++17
11 / 100
 3000 ms 36092 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();
        if(pos[cur]) continue;
        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 9676 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 9640 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 5 ms 9676 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 6 ms 9676 KB Output is correct
9 Correct 6 ms 9676 KB Output is correct
10 Correct 6 ms 9676 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 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 9640 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 5 ms 9676 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 6 ms 9676 KB Output is correct
9 Correct 6 ms 9676 KB Output is correct
10 Correct 6 ms 9676 KB Output is correct
11 Correct 175 ms 9880 KB Output is correct
12 Correct 175 ms 9864 KB Output is correct
13 Correct 184 ms 9856 KB Output is correct
14 Correct 176 ms 9860 KB Output is correct
15 Correct 90 ms 9804 KB Output is correct
16 Correct 104 ms 9876 KB Output is correct
17 Correct 105 ms 9932 KB Output is correct
18 Correct 95 ms 9932 KB Output is correct
19 Correct 99 ms 9928 KB Output is correct
20 Correct 98 ms 9932 KB Output is correct
21 Correct 101 ms 9932 KB Output is correct
22 Correct 100 ms 9932 KB Output is correct
23 Correct 126 ms 9932 KB Output is correct
24 Correct 97 ms 9884 KB Output is correct
25 Correct 145 ms 10060 KB Output is correct
26 Correct 158 ms 9932 KB Output is correct
27 Correct 138 ms 9952 KB Output is correct
28 Correct 117 ms 9932 KB Output is correct
29 Correct 118 ms 9932 KB Output is correct
30 Correct 118 ms 9908 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3071 ms 36092 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 9676 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 9640 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 5 ms 9676 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 6 ms 9676 KB Output is correct
9 Correct 6 ms 9676 KB Output is correct
10 Correct 6 ms 9676 KB Output is correct
11 Correct 175 ms 9880 KB Output is correct
12 Correct 175 ms 9864 KB Output is correct
13 Correct 184 ms 9856 KB Output is correct
14 Correct 176 ms 9860 KB Output is correct
15 Correct 90 ms 9804 KB Output is correct
16 Correct 104 ms 9876 KB Output is correct
17 Correct 105 ms 9932 KB Output is correct
18 Correct 95 ms 9932 KB Output is correct
19 Correct 99 ms 9928 KB Output is correct
20 Correct 98 ms 9932 KB Output is correct
21 Correct 101 ms 9932 KB Output is correct
22 Correct 100 ms 9932 KB Output is correct
23 Correct 126 ms 9932 KB Output is correct
24 Correct 97 ms 9884 KB Output is correct
25 Correct 145 ms 10060 KB Output is correct
26 Correct 158 ms 9932 KB Output is correct
27 Correct 138 ms 9952 KB Output is correct
28 Correct 117 ms 9932 KB Output is correct
29 Correct 118 ms 9932 KB Output is correct
30 Correct 118 ms 9908 KB Output is correct
31 Execution timed out 3071 ms 36092 KB Time limit exceeded
32 Halted 0 ms 0 KB -