Submission #1050248

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050248		hotboy2703	Capital City (JOI20_capital_city)	C++17	100 / 100	141 ms	53768 KiB

capital_city

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXN = 2e5+100;
vector <ll> g[MAXN];
ll in[MAXN],out[MAXN],timeDFS;
ll c[MAXN];
ll n,k;
vector <ll> color[MAXN];
namespace SCC{
    vector <ll> edge[MAXN];
    vector <ll> rev[MAXN];
    bool in[MAXN];
    void add(ll x,ll y){
        // cout<<x<<' '<<y<<'\n';
        edge[x].push_back(y);
        rev[y].push_back(x);
    }
    void dfs(ll u,vector <ll> gg[],vector <ll> &comp){
        in[u] = 1;
        for (auto v:gg[u]){
            if (!in[v]){
                dfs(v,gg,comp);
            }
        }
        comp.push_back(u);
    }
    ll solve(){
        vector <ll> order;
        for (ll i = 1;i <= k;i ++){
            if (!in[i]){
                dfs(i,edge,order);
            }
        }
        memset(in,0,sizeof in);
        reverse(order.begin(),order.end());
        ll res = k;
        for (auto x:order){
            if (!in[x]){
                vector <ll> comp;
                dfs(x,rev,comp);
                bool ok = 1;
                for (auto x:comp){
                    for (auto y:edge[x]){
                        if (!in[y]){ok=0;}
                    }
                }
                if (ok && sz(comp) < res){
                    res = sz(comp);
                }
            }
        }
        return res;
    }
}
void dfs(ll u,ll p){
    in[u] = ++timeDFS;
    color[c[u]].push_back(in[u]);
    for (auto v:g[u]){
        if (v==p)continue;
        dfs(v,u);
    }
    out[u] = timeDFS;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);
    cin>>n>>k;
    for (ll i = 1;i < n;i ++){
        ll u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (ll i = 1;i <= n;i ++)cin>>c[i];
    dfs(1,1);
    for (ll i = 1;i <= n;i ++){
        for (auto v:g[i]){
            if (c[v] != c[i]){
                if (in[v] > in[i]){
                    auto tmp = lower_bound(color[c[i]].begin(),color[c[i]].end(),in[v]);
                    if (tmp!=color[c[i]].end() && (*tmp) <= out[v]){
                        SCC::add(c[i],c[v]);
                    }
                }
                else{
                    auto tmp = upper_bound(color[c[i]].begin(),color[c[i]].end(),out[i]) - lower_bound(color[c[i]].begin(),color[c[i]].end(),in[i]);
                    if (tmp != sz(color[c[i]]))SCC::add(c[i],c[v]);
                }
            }
        }
    }
    cout<<SCC::solve()-1;
}

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