oj.uz

Submission #915256

# Submission time Handle Problem Language Result Execution time Memory
915256 2024-01-23T15:05:03 Z Tuanlinh123 Capital City (JOI20_capital_city) C++17
0 / 100
 227 ms 218796 KB 
#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]) lo[u]=min(lo[u], num[v]);
        else
        {
            dfs2(v), lo[u]=min(lo[u], lo[v]);
            if (lo[v]>num[u]) ok=0;
        }
    }
    if (lo[u]==num[u])
    {
        cnt++, sz[cnt]=ok?1:inf;
        while (st.top()!=u)
        {
            comp[st.top()]=cnt, sz[cnt]++;
            num[st.top()]=inf, st.pop();
        }
        num[u]=inf, comp[u]=cnt, 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

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)]);
      |                                                    ~^~

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 68184 KB Output is correct
2 Correct 19 ms 68084 KB Output is correct
3 Correct 18 ms 68188 KB Output is correct
4 Incorrect 18 ms 68188 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 68184 KB Output is correct
2 Correct 19 ms 68084 KB Output is correct
3 Correct 18 ms 68188 KB Output is correct
4 Incorrect 18 ms 68188 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 227 ms 218796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 68184 KB Output is correct
2 Correct 19 ms 68084 KB Output is correct
3 Correct 18 ms 68188 KB Output is correct
4 Incorrect 18 ms 68188 KB Output isn't correct
5 Halted 0 ms 0 KB -