oj.uz

Submission #1027376

# Submission time Handle Problem Language Result Execution time Memory
1027376 2024-07-19T05:26:49 Z adaawf Capital City (JOI20_capital_city) C++17
1 / 100
 257 ms 46540 KB 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> g[200005], v[200005], vv;
int c[200005], dd[200005], da[200005], db[200005], a[200005];
int tn[200005], tt[200005], d[200005], s[200005], z = 0;
void dfs(int x, int p) {
    tn[x] = ++z;
    s[x] = 1;
    c[a[x]]++;
    d[x] = p;
    for (int w : g[x]) {
        if (w == p || dd[w] == 1) continue;
        dfs(w, x);
        s[x] += s[w];
    }
    tt[x] = z;
}
void dfs2(int x, int p) {
    da[a[x]] = db[x] = c[a[x]] = 0;
    for (int w : g[x]) {
        if (w == p || dd[w] == 1) continue;
        dfs2(w, x);
    }
}
int centroid(int x, int p, int h) {
    for (int w : g[x]) {
        if (w == p || dd[w] == 1) continue;
        if (s[w] > h / 2) {
            return centroid(w, x, h);
        }
    }
    return x;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, k, mi = 1e9;
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        v[a[i]].push_back(i);
    }
    queue<int> q;
    q.push(1);
    while (!q.empty()) {
        int p = q.front();
        q.pop();
        if (dd[p] == 1) continue;
        z = 0;
        dfs(p, -1);
        int h = centroid(p, -1, s[p]), flag = 0, k = h, res = 0;
        vv.push_back(a[h]);
        da[a[h]] = 1;
        for (int i = 0; i < vv.size(); i++) {
            int w = vv[i];
            if (c[w] != v[w].size()) {
                flag = 1;
                break;
            }
            res++;
            for (int ww : v[w]) {
                while (tn[k] > tn[ww] || tt[k] < tt[ww]) {
                    k = d[k];
                    db[k] = 1;
                    if (da[a[k]] == 0) {
                        vv.push_back(a[k]);
                        da[a[k]] = 1;
                    }
                }
                int h = ww;
                while (db[h] == 0 && h != d[k]) {
                    if (da[a[h]] == 0) {
                        vv.push_back(a[h]);
                        da[a[h]] = 1;
                    }
                    db[h] = 1;
                    h = d[h];
                }
            }
        }
        if (flag == 0) mi = min(mi, res - 1);
        dfs2(p, -1);
        dd[h] = 1;
        for (int w : g[h]) {
            if (dd[w] == 0) {
                q.push(w);
            }
        }
    }
    cout << mi;
}

Compilation message

capital_city.cpp: In function 'int main()':
capital_city.cpp:62:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for (int i = 0; i < vv.size(); i++) {
      |                         ~~^~~~~~~~~~~
capital_city.cpp:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             if (c[w] != v[w].size()) {
      |                 ~~~~~^~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14428 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 2 ms 12796 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 3 ms 12636 KB Output is correct
9 Correct 2 ms 12636 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14428 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 2 ms 12796 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 3 ms 12636 KB Output is correct
9 Correct 2 ms 12636 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Correct 4 ms 14684 KB Output is correct
12 Correct 4 ms 14684 KB Output is correct
13 Correct 5 ms 12636 KB Output is correct
14 Correct 4 ms 14684 KB Output is correct
15 Incorrect 4 ms 14684 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 45796 KB Output is correct
2 Correct 130 ms 46540 KB Output is correct
3 Correct 257 ms 45520 KB Output is correct
4 Correct 119 ms 46540 KB Output is correct
5 Incorrect 239 ms 42700 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14428 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 2 ms 12796 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 3 ms 12636 KB Output is correct
9 Correct 2 ms 12636 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Correct 4 ms 14684 KB Output is correct
12 Correct 4 ms 14684 KB Output is correct
13 Correct 5 ms 12636 KB Output is correct
14 Correct 4 ms 14684 KB Output is correct
15 Incorrect 4 ms 14684 KB Output isn't correct
16 Halted 0 ms 0 KB -