Submission #1278928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278928		denislav	Capital City (JOI20_capital_city)	C++20	31 / 100	354 ms	100632 KiB

capital_city

# include <iostream>
# include <vector>
# include <algorithm>
# include <set>
using namespace std;

const int MAX=2e5+11;

int n,k,root;
vector<int> adj[MAX];
int col[MAX];

int ct;
int a[MAX];
void dfs_init(int curr, int par)
{
    ct++;
    a[ct]=col[curr];
    for(int nxt: adj[curr])
    {
        if(nxt==par) continue;
        dfs_init(nxt,curr);
    }
}

vector<int> app[MAX];
vector<int> g[MAX*4];
vector<int> g2[MAX*4];
int col2[MAX*4];
int leaf[MAX];

void add_edge(int u, int v)
{
    //if(v/2!=u) cout<<u<<"->"<<v<<"\n";
    g[u].push_back(v);
    g2[v].push_back(u);
}

void build(int v=1, int l=1, int r=n)
{
    if(l==r)
    {
        leaf[l]=v;
        if(app[a[l]].size()!=0) add_edge(leaf[app[a[l]].back()],v);
        app[a[l]].push_back(l);

        col2[v]=a[l];
        return ;
    }

    int mid=(l+r)/2;
    add_edge(v,v*2);
    add_edge(v,v*2+1);
    build(v*2,l,mid);
    build(v*2+1,mid+1,r);
}

void add(int from, int le, int ri, int v=1, int l=1, int r=n)
{
    if(ri<l or r<le) return ;
    if(le<=l and r<=ri)
    {
        //cout<<from<<"-->"<<l<<" "<<r<<"\n";
        add_edge(from,v);
        return ;
    }

    int mid=(l+r)/2;
    add(from,le,ri,v*2,l,mid);
    add(from,le,ri,v*2+1,mid+1,r);
}

bool vis[MAX*4];
vector<int> order;

void dfs_order(int curr)
{
    vis[curr]=1;
    for(int nxt: g[curr])
    {
        if(!vis[nxt]) dfs_order(nxt);
    }
    order.push_back(curr);
}

set<int> s;
vector<int> nodes;
void dfs_scc(int curr)
{
    nodes.push_back(curr);
    vis[curr]=1;
    if(col2[curr]!=0) s.insert(col2[curr]);

    for(int nxt: g2[curr])
    {
        if(!vis[nxt]) dfs_scc(nxt);
    }
}

void scc()
{
    for(int i=1;i<=n*4;i++)
    {
        if(!vis[i]) dfs_order(i);
    }
    for(int i=1;i<=n*4;i++) vis[i]=0;
    reverse(order.begin(),order.end());

    int ans=1e9;
    for(int x: order)
    {
        if(!vis[x])
        {
            s.clear();
            nodes.clear();
            dfs_scc(x);
            if(s.size()==0) continue;

            bool f=1;
            for(int curr: nodes)
            {
                for(int nxt: g[curr]) if(!vis[nxt]) f=0;
            }

            if(f)
            {
                ans=min(ans,(int)s.size());
                //cout<<"->";
                //for(int x: s) cout<<x<<" ";
                //cout<<"\n";
            }


        }
    }

    cout<<ans-1<<"\n";
}

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

    cin>>n>>k;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i=1;i<=n;i++) cin>>col[i];
    for(int i=1;i<=n;i++) if(adj[i].size()==1) {root=i;break;}

    if(n==1)
    {
        cout<<0<<"\n";
        return 0;
    }

    dfs_init(root,0);
    build();

    //for(int i=1;i<=n;i++) cout<<a[i]<<" ";
    //cout<<"\n";

    //cout<<"\n";
    for(int i=1;i<=k;i++)
    {
        int l=app[i][0],r=app[i].back();
        add_edge(leaf[r],leaf[l]);
        add(leaf[l],l,r);
        //cout<<i<<":"<<l<<" "<<r<<"\n";
    }

    scc();

    return 0;
}

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