Submission #915266

#	Time	Username	Problem	Language	Result	Execution time	Memory
915266		Tuanlinh123	Capital City (JOI20_capital_city)	C++17	100 / 100	261 ms	221036 KiB

capital_city

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

const ll maxn=1000005, inf=1e9;
stack <ll> st;
vector <pll> euler;
pll sp[20][maxn*2]; 
vector <ll> A[maxn], B[maxn];
ll c[maxn], lca[maxn], pa[maxn], r[maxn];
ll cnt, Time, num[maxn], lo[maxn], comp[maxn], sz[maxn];

void dfs(ll u)
{
    lca[u]=euler.size()+1;
    euler.pb({lca[u], u});
    for (ll v:A[u])
    {
        if (v==pa[u])
            continue;
        pa[v]=u, dfs(v);
        euler.pb({lca[u], u});
    }
}

void initlca()
{
    ll n=euler.size();
    for (ll i=0; i<n; i++)
        sp[0][i+1]=euler[i];
    for (ll i=1; i<20; i++)
        for (ll j=1; j+(1<<i)<=n+1; j++)
            sp[i][j]=min(sp[i-1][j], sp[i-1][j+(1<<i-1)]);
}

ll LCA(ll u, ll v)
{
    ll l=lca[u], r=lca[v];
    if (l>r) swap(l, r);
    ll j=__lg(r-l+1);
    return min(sp[j][l], sp[j][r-(1<<j)+1]).se;
}

void dfs2(ll u)
{
    bool ok=1;
    st.push(u);
    lo[u]=num[u]=++Time;
    for (ll v:B[u])
    {
        if (num[v])
        {
            if (comp[v]) comp[u]=inf;
            lo[u]=min(lo[u], num[v]);
        } 
        else
        {
            dfs2(v), lo[u]=min(lo[u], lo[v]);
            if (comp[v]) comp[u]=inf;
        }
    }
    if (lo[u]==num[u])
    {
        cnt++;
        while (st.top()!=u)
        {
            if (comp[st.top()]) sz[cnt]=inf;
            else comp[st.top()]=cnt, sz[cnt]++;
            num[st.top()]=inf, st.pop();
        }
        if (comp[st.top()]) sz[cnt]=inf;
        else comp[st.top()]=cnt, sz[cnt]++;
        num[st.top()]=inf, st.pop();
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, k, ans=inf; cin >> n >> k;
    for (ll i=1; i<n; i++)
    {
        ll u, v; cin >> u >> v;
        A[u].pb(v); A[v].pb(u);
    }
    dfs(1), initlca();
    for (ll i=1; i<=n; i++) 
    {
        cin >> c[i];
        if (!r[c[i]]) r[c[i]]=i;
        else r[c[i]]=LCA(r[c[i]], i);
    }
    for (ll i=1; i<=n; i++)
        if (pa[i] && i!=r[c[i]])
            B[c[i]].pb(c[pa[i]]);
    for (ll i=1; i<=k; i++)
        if (!num[i])
            dfs2(i);
    for (ll i=1; i<=cnt; i++)
        ans=min(ans, sz[i]-1);
    cout << ans << "\n";
}

Compilation message (stderr)

capital_city.cpp: In function 'void initlca()':
capital_city.cpp:39:53: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   39 |             sp[i][j]=min(sp[i-1][j], sp[i-1][j+(1<<i-1)]);
      |                                                    ~^~
capital_city.cpp: In function 'void dfs2(long long int)':
capital_city.cpp:52:10: warning: unused variable 'ok' [-Wunused-variable]
   52 |     bool ok=1;
      |          ^~

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