Submission #1124623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124623		denislav	Capital City (JOI20_capital_city)	C++20	0 / 100	1229 ms	45096 KiB

capital_city

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

const int MAX=2e5+11;

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

bool kill[MAX];
int sz[MAX];

int last[MAX];
bool add[MAX];
int cnt[MAX];

void dfs_sz(int curr, int par)
{
    sz[curr]=1;
    last[col[curr]]=0;
    add[col[curr]]=0;
    cnt[col[curr]]=0;

    for(int nxt: adj[curr])
    {
        if(nxt==par or kill[nxt]) continue;

        dfs_sz(nxt,curr);
        sz[curr]+=sz[nxt];
    }
}

int get_centroid(int curr, int par, int N)
{
    for(int nxt: adj[curr])
    {
        if(nxt==par or kill[nxt]) continue;
        if(sz[nxt]*2>N) return get_centroid(nxt,curr,N);
    }

    return curr;
}

void dfs_add(int curr, int par, int from)
{
    if(last[col[curr]]!=from) add[col[curr]]=1;
    last[col[curr]]=from;

    for(int nxt: adj[curr])
    {
        if(nxt==par or kill[nxt]) continue;
        dfs_add(nxt,curr,from);
    }
}

int Limit;
set<int> s;
map<int, bool> colors[MAX];
bool over[MAX];

void dfs(int curr, int par)
{
    cnt[col[curr]]++;
    if(cnt[col[curr]]==1) s.insert(col[curr]);

    if(!over[col[curr]])
    {
        if((int)s.size()>=Limit)
        {
            over[col[curr]]=1;
        }
        else
        {
            for(int x: s) colors[col[curr]][x]=1;
            if((int)colors[col[curr]].size()>=Limit) over[col[curr]]=1;
        }
    }

    for(int nxt: adj[curr])
    {
        if(nxt==par or kill[nxt]) continue;
        dfs(nxt,curr);
    }

    cnt[col[curr]]--;
    if(cnt[col[curr]]==0) s.erase(col[curr]);
}

void centroid_dc(int curr)
{
    dfs_sz(curr,0);
    curr=get_centroid(curr,0,sz[curr]);

    last[col[curr]]=curr;
    for(int nxt: adj[curr])
    {
        if(kill[nxt]) continue;
        dfs_add(nxt,curr,nxt);
    }

    for(int nxt: adj[curr])
    {
        if(kill[nxt]) continue;
        dfs(nxt,curr);

    }

    kill[curr]=1;
    for(int nxt: adj[curr])
    {
        if(kill[nxt]) continue;
        centroid_dc(nxt);
    }
}

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];

    Limit=sqrt(n)+3;
    centroid_dc(1);

    int ans=Limit;
    for(int i=1;i<=k;i++)
    {
        if(over[i]) continue;

        int curr_ans=colors[i].size();
        if(colors[i].find(i)==colors[i].end()) curr_ans--;
        ans=min(ans,curr_ans);

        //cout<<i<<":"<<"\n";
        //for(pair<int, bool> pa: colors[i]) cout<<pa.first<<" ";
        //cout<<"\n";
    }

    cout<<ans<<"\n";

    return 0;
}

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