oj.uz

Submission #937515

# Submission time Handle Problem Language Result Execution time Memory
937515 2024-03-04T07:42:38 Z velislavgarkov Capital City (JOI20_capital_city) C++14
1 / 100
 397 ms 51540 KB 
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int MAXN=2e5+10;
const int INF=1e9;
vector <int> diff;
vector <int> v[MAXN], vc[MAXN], ch[MAXN];
int col[MAXN], ans;
int par[MAXN], in[MAXN], out[MAXN], cnt;
int d[MAXN];
bool seen[MAXN], used[MAXN];
int n, k;
void find_ss(int x, int p) {
    d[x]=1;
    for (auto i:v[x]) {
        if (i==p || seen[i]) continue;
        find_ss(i,x);
        d[x]+=d[i];
    }
}
int find_centroid(int x, int ss) {
    for (auto i:v[x]) {
        if (seen[x]) continue;
        if (d[i]>d[x]) continue;
        if (d[i]*2>ss) return find_centroid(i,ss);
    }
    return x;
}
int decompose(int x) {
    find_ss(x,-1);
    int cur=find_centroid(x,d[x]);
    seen[cur]=true;
    for (auto i:v[cur]) {
        if (seen[i]) continue;
        int to=decompose(i);
        ch[cur].push_back(to);
    }
    return cur;
}
void dfs_cent(int x) {
    in[x]=cnt;
    cnt++;
    for (auto i:ch[x]) dfs_cent(i);
    out[x]=cnt;
    cnt++;
}
void dfs(int x, int p) {
    for (auto i:v[x]) {
        if (i==p || seen[i]) continue;
        par[i]=x;
        dfs(i,x);
    }
}
bool in_subtree(int x, int i) {
    return (in[x]<=in[i] && out[x]>=out[i]);
}
void bfs_ans(int start) {
    if (!diff.empty()) diff.clear();
    queue <int> q;
    diff.push_back(col[start]);
    q.push(col[start]);
    used[col[start]]=true;
    int s=0;
    bool fl=false;
    while (!q.empty()) {
        int x=q.front();
        q.pop();
        s++;
        for (auto i:vc[x]) {
            if (!in_subtree(start,i)) {
                fl=true;
                break;
            }
            if (par[i]!=0 && !used[col[par[i]]]) {
                used[col[par[i]]]=true;
                q.push(col[par[i]]);
                diff.push_back(col[par[i]]);
            }
        }
        if (fl) break;
    }
    if (!fl) ans=min(ans,s-1);
    for (auto i:diff) used[i]=false;
}
void find_ans(int x) {
    dfs(x,-1);
    bfs_ans(x);
    seen[x]=true;
    for (auto i:ch[x]) find_ans(i);
}
int main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a, b;
    cin >> n >> k;
    for (int i=0;i<n-1;i++) {
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for (int i=1;i<=n;i++) {
        cin >> col[i];
        vc[col[i]].push_back(i);
    }
    ans=INF;
    int start=decompose(1);
    dfs_cent(start);
    for (int i=1;i<=n;i++) seen[i]=false;
    find_ans(start);
    cout << ans << endl;
    return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 18524 KB Output is correct
2 Correct 4 ms 18672 KB Output is correct
3 Correct 4 ms 18524 KB Output is correct
4 Correct 5 ms 18524 KB Output is correct
5 Correct 5 ms 18676 KB Output is correct
6 Correct 4 ms 18520 KB Output is correct
7 Correct 4 ms 18524 KB Output is correct
8 Correct 4 ms 18524 KB Output is correct
9 Correct 5 ms 18520 KB Output is correct
10 Correct 4 ms 18520 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 18524 KB Output is correct
2 Correct 4 ms 18672 KB Output is correct
3 Correct 4 ms 18524 KB Output is correct
4 Correct 5 ms 18524 KB Output is correct
5 Correct 5 ms 18676 KB Output is correct
6 Correct 4 ms 18520 KB Output is correct
7 Correct 4 ms 18524 KB Output is correct
8 Correct 4 ms 18524 KB Output is correct
9 Correct 5 ms 18520 KB Output is correct
10 Correct 4 ms 18520 KB Output is correct
11 Correct 5 ms 18776 KB Output is correct
12 Correct 5 ms 18780 KB Output is correct
13 Correct 5 ms 18780 KB Output is correct
14 Correct 5 ms 18776 KB Output is correct
15 Correct 5 ms 18684 KB Output is correct
16 Correct 5 ms 18712 KB Output is correct
17 Correct 5 ms 18780 KB Output is correct
18 Incorrect 5 ms 18780 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 51148 KB Output is correct
2 Correct 180 ms 51540 KB Output is correct
3 Correct 322 ms 50516 KB Output is correct
4 Correct 148 ms 51436 KB Output is correct
5 Correct 341 ms 47696 KB Output is correct
6 Correct 176 ms 51536 KB Output is correct
7 Correct 323 ms 48204 KB Output is correct
8 Correct 153 ms 51364 KB Output is correct
9 Correct 397 ms 46572 KB Output is correct
10 Incorrect 356 ms 43896 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 18524 KB Output is correct
2 Correct 4 ms 18672 KB Output is correct
3 Correct 4 ms 18524 KB Output is correct
4 Correct 5 ms 18524 KB Output is correct
5 Correct 5 ms 18676 KB Output is correct
6 Correct 4 ms 18520 KB Output is correct
7 Correct 4 ms 18524 KB Output is correct
8 Correct 4 ms 18524 KB Output is correct
9 Correct 5 ms 18520 KB Output is correct
10 Correct 4 ms 18520 KB Output is correct
11 Correct 5 ms 18776 KB Output is correct
12 Correct 5 ms 18780 KB Output is correct
13 Correct 5 ms 18780 KB Output is correct
14 Correct 5 ms 18776 KB Output is correct
15 Correct 5 ms 18684 KB Output is correct
16 Correct 5 ms 18712 KB Output is correct
17 Correct 5 ms 18780 KB Output is correct
18 Incorrect 5 ms 18780 KB Output isn't correct
19 Halted 0 ms 0 KB -