Submission #959180

#	Time	Username	Problem	Language	Result	Execution time	Memory
959180		andrei_boaca	Capital City (JOI20_capital_city)	C++17	11 / 100	3033 ms	382160 KiB

capital_city

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
int n,k,nr[200005];
bool use[200005];
vector<int> mynodes[200005];
int cul[200005];
vector<int> muchii[200005];
vector<int> edges[200005];
vector<pii> g;
vector<int> st;
vector<pii> init;
int comp[200005],nrcul[200005],nrcomp,nrnodes[200005],nrmuchii[200005];
int root;
void dfs1(int nod)
{
    use[nod]=1;
    for(int i:edges[nod])
        if(!use[i])
            dfs1(i);
    st.push_back(nod);
}
void dfs2(int nod)
{
    use[nod]=1;
    comp[nod]=nrcomp;
    nrcul[nrcomp]++;
    for(int i:edges[nod])
        if(!use[i])
            dfs2(i);
}
void dfs(int nod)
{
    use[nod]=1;
    nr[nod]=0;
    nr[nod]=(cul[nod]==cul[root]);
    for(int i:muchii[nod])
        if(!use[i])
        {
            dfs(i);
            nr[nod]+=nr[i];
        }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        muchii[a].push_back(b);
        muchii[b].push_back(a);
        init.push_back({a,b});
    }
    for(int i=1;i<=n;i++)
    {
        cin>>cul[i];
        mynodes[cul[i]].push_back(i);
    }
    for(int c=1;c<=k;c++)
    {
        root=mynodes[c][0];
        for(int i=1;i<=n;i++)
            use[i]=0;
        dfs(root);
        for(int i=1;i<=n;i++)
            if(nr[i]>0&&cul[i]!=c)
            {
                edges[c].push_back(cul[i]);
                g.push_back({c,cul[i]});
            }
    }
    for(int i=1;i<=k;i++)
        use[i]=0;
    for(int i=1;i<=k;i++)
        if(!use[i])
            dfs1(i);
    reverse(st.begin(),st.end());
    for(int i=1;i<=k;i++)
    {
        use[i]=0;
        edges[i].clear();
    }
    for(pii p:g)
        edges[p.second].push_back(p.first);
    for(int i:st)
        if(!use[i])
        {
            nrcomp++;
            dfs2(i);
        }
    for(int i=1;i<=n;i++)
    {
        int c=comp[cul[i]];
        nrnodes[c]++;
    }
    for(pii p:init)
    {
        int a=p.first;
        int b=p.second;
        a=comp[cul[a]];
        b=comp[cul[b]];
        if(a==b)
            nrmuchii[a]++;
    }
    int ans=1e9;
    for(int i=1;i<=nrcomp;i++)
        if(nrmuchii[i]+1==nrnodes[i])
            ans=min(ans,nrcul[i]);
    cout<<ans-1;
    return 0;
}

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