Submission #1272290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272290		baotoan655	수도 (JOI20_capital_city)	C++20	100 / 100	427 ms	81304 KiB

capital_city

#include <bits/stdc++.h>
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;

const int N = 2e5 + 5;
vector<int> g[N];
int n, K;
int c[N];
vector<int> city[N];

int in[N], tour[N], sz[N], time_dfs, fa[N];
void pre_dfs(int u) {
    sz[u] = 1;
    for(int v : g[u]) if(v != fa[u]) {
        fa[v] = u;
        pre_dfs(v);
        sz[u] += sz[v];
    }
}
int chainId[N], chainRoot[N], curChain;
void hld(int u) {
    if(!chainId[u]) {
        chainId[u] = ++curChain;
        chainRoot[curChain] = u;
    }
    in[u] = ++time_dfs;
    tour[time_dfs] = u;
    int hc = -1;
    for(int v : g[u]) if(v != fa[u]) {
        if(hc == -1 || sz[v] > sz[hc]) hc = v;
    }
    if(hc != -1) {
        chainId[hc] = chainId[u];
        hld(hc);
    }
    for(int v : g[u]) if(v != fa[u] && v != hc) {
        hld(v);
    }
}
vector<int> adj[5 * N];
int num;
int it[N << 2];
void build(int k, int l, int r) {
    it[k] = ++num;
    if(l == r) {
        // cout << it[k] << ' ' << c[tour[l]] << '\n';
        adj[it[k]].emplace_back(c[tour[l]]);
        return;
    }
    int mid = l + r >> 1;
    build(k << 1, l, mid);
    build(k << 1 | 1, mid + 1, r);
    adj[it[k]].emplace_back(it[k << 1]);
    adj[it[k]].emplace_back(it[k << 1 | 1]);
}

void update(int k, int l, int r, int u, int v, int par) {
    if(u <= l && r <= v) {
        // cout << par << ' ' << it[k] << '\n';
        adj[par].emplace_back(it[k]);
        return;
    }
    int mid = l + r >> 1;
    if(mid >= u) update(k << 1, l, mid, u, v, par);
    if(mid + 1 <= v) update(k << 1 | 1, mid + 1, r, u, v, par);
}
void add(int u, int v, int par) {
    // cout << u << ' ' << v << ' ' << par << '\n';
    while(chainId[u] != chainId[v]) {
        if(chainId[u] > chainId[v]) {
            update(1, 1, n, in[chainRoot[chainId[u]]], in[u], par);
            u = fa[chainRoot[chainId[u]]];
        } else {
            update(1, 1, n, in[chainRoot[chainId[v]]], in[v], par);
            v = fa[chainRoot[chainId[v]]];
        }
    }
    if(in[u] < in[v]) update(1, 1, n, in[u], in[v], par);
    else update(1, 1, n, in[v], in[u], par);
}
int dfn[5 * N], low[5 * N], id[5 * N], scc, tim, deg[5 * N];
int dp[5 * N];
stack<int> stk;
void tarjan(int u) {
    dfn[u] = low[u] = ++tim;
    stk.emplace(u);
    for(int v : adj[u]) {
        if(id[v]) continue;
        if(!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(low[u] == dfn[u]) {
        for(++scc; true; ) {
            int v = stk.top();
            stk.pop();
            id[v] = scc;
            if(u == v) break;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    file("A") else file("task");
    cin >> n >> K;
    for(int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    for(int i = 1; i <= n; ++i) {
        cin >> c[i];
        city[c[i]].emplace_back(i);
    }
    
    pre_dfs(1);
    hld(1);
    num = K;
    build(1, 1, n);
    for(int i = 1; i <= K; ++i) {
        for(int j = 0; j < (int)city[i].size() - 1; ++j) {
            add(city[i][j], city[i][j + 1], i);
        }
    }

    for(int i = 1; i <= num; ++i) if(!dfn[i]) tarjan(i);
    for(int i = 1; i <= K; ++i) {
        dp[id[i]]++;
    }
    for(int i = 1; i <= num; ++i) for(int j : adj[i]) {
        if(id[i] != id[j]) {
            ++deg[id[i]];
        }
    }
    int ans = K;
    for(int i = 1; i <= scc; ++i) if(deg[i] == 0) {
        ans = min(ans, dp[i] - 1);
    }
    cout << ans << '\n';
    return 0;
}

Compilation message (stderr)

capital_city.cpp: In function 'int main()':
capital_city.cpp:2:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
capital_city.cpp:110:5: note: in expansion of macro 'file'
  110 |     file("A") else file("task");
      |     ^~~~
capital_city.cpp:2:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
capital_city.cpp:110:5: note: in expansion of macro 'file'
  110 |     file("A") else file("task");
      |     ^~~~
capital_city.cpp:2:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
capital_city.cpp:110:20: note: in expansion of macro 'file'
  110 |     file("A") else file("task");
      |                    ^~~~
capital_city.cpp:2:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
capital_city.cpp:110:20: note: in expansion of macro 'file'
  110 |     file("A") else file("task");
      |                    ^~~~

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 59 / 59