Submission #1117370

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117370		Zero_OP	Capital City (JOI20_capital_city)	C++14	100 / 100	187 ms	51228 KiB

capital_city

#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for(int i = (l); i < (r); ++i)
#define sz(v) (int)v.size()
#define dbg(x) "[" #x " = " << (x) << "]"
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define file(name) if(fopen(name".inp", "r")){ freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

template<typename T>
    bool minimize(T& a, const T& b){
        if(a > b){
            return a = b, true;
        }
        return false;
    }

template<typename T>
    bool maximize(T& a, const T& b){
        if(a < b){
            return a = b, true;
        }
        return false;
    }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using vi = vector<int>;
using vl = vector<ll>;

const int MAX = 2e5 + 5;

int N, K, timer_dfs, tin[MAX], tout[MAX], c[MAX], par[MAX], tour[MAX];
vi adj[MAX], group[MAX], adj_color[MAX];

int low[MAX], num[MAX], cnt[MAX], bad[MAX], id[MAX], num_scc;
stack<int> st;

void dfs(int u, int p){
    tour[tin[u] = ++timer_dfs] = u;
    for(int v : adj[u]) if(v != p){
        par[v] = u;
        dfs(v, u);
    }
    tout[u] = timer_dfs;
}

void dfs_tarjan(int u){
    low[u] = num[u] = ++timer_dfs;
    st.push(u);

    for(int v : adj_color[u]){
        if(num[v]) minimize(low[u], num[v]);
        else{
            dfs_tarjan(v);
            minimize(low[u], low[v]);
        }
    }

    if(low[u] == num[u]){
        int v;
        ++num_scc;
        do{
            v = st.top(); st.pop();
            low[v] = num[v] = MAX;
            id[v] = num_scc;
            ++cnt[num_scc];
        } while(v != u);
    }
}

bool in_subtree(int u, int v){
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

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

    file("task");

    cin >> N >> K;
    for(int i = 1; i < N; ++i){
        int u, v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }

    for(int i = 1; i <= N; ++i){
        cin >> c[i];
    }

    dfs(1, -1);

    for(int i = 1; i <= N; ++i){
        group[c[i]].emplace_back(tin[i]);
    }

    for(int i = 2; i <= N; ++i){
        int j = par[i];
        if(c[i] == c[j]) continue;

        int p = lower_bound(all(group[c[j]]), tin[i]) - group[c[j]].begin();
        if(p < sz(group[c[j]]) && group[c[j]][p] <= tout[i]){
            adj_color[c[j]].emplace_back(c[i]); //c[j] need c[i]
        }

        if(!(in_subtree(i, tour[group[c[i]].front()]) && in_subtree(i, tour[group[c[i]].back()]))){
            adj_color[c[i]].emplace_back(c[j]); //c[i] need c[j]
        }
    }

    int ans = K;

    for(int i = 1; i <= K; ++i){
        if(!num[i]) dfs_tarjan(i);
    }

    for(int i = 1; i <= K; ++i){
        for(int j : adj_color[i]){
            if(id[i] != id[j]){
                bad[id[i]] = true;
            }
        }
    }

    for(int i = 1; i <= num_scc; ++i){
        if(!bad[i]) ans = min(ans, cnt[i] - 1);
    }

    cout << ans << '\n';

    return 0;
}

Compilation message (stderr)

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

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