Submission #1027404

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027404		adaawf	Capital City (JOI20_capital_city)	C++17	100 / 100	414 ms	45288 KiB

capital_city

#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;
        vv.clear();
        for (int w : g[h]) {
            if (dd[w] == 0) {
                q.push(w);
            }
        }
    }
    cout << mi;
}

Compilation message (stderr)

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 / 1
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 59 / 59