Submission #942420

#	Time	Username	Problem	Language	Result	Execution time	Memory
942420		groshi	Capital City (JOI20_capital_city)	C++17	100 / 100	401 ms	47952 KiB

capital_city

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct wi{
    vector<int> Q;
    int wiel=0;
    int kto=0;
    int ojc;
}*w;
vector<int> lista[300000];
int wynik=1e9;
int byl[300000];
int odw[300000];
int kolor[300000];
int licz_wiel(int x,int ojc=-1)
{
	w[x].wiel=1;
	for(int child:w[x].Q)
	{
		if(child==ojc || byl[child])
            continue;
		w[x].wiel+=licz_wiel(child,x);
	}
	return w[x].wiel;
}
int licz_centr(int x,int wiel,int ojc=-1)
{
	for(int child:w[x].Q)
	{
		if(child==ojc || byl[child])
            continue;
		if(w[child].wiel*2>wiel)
			return licz_centr(child,wiel,x);
	}
	return x;
}
void dfs(int x,int ojc,int kto)
{
    w[x].kto=kto;
    w[x].ojc=ojc;
    for(int i:w[x].Q)
    {
        if(i==ojc || byl[i])
            continue;
        dfs(i,x,kto);
    }
}
void centroid(int x)
{
	int c=licz_centr(x,licz_wiel(x));
	byl[c]=1;
	dfs(c,c,c);
	queue<int> kolejka;
	kolejka.push(kolor[c]);
	int wynikk=0;
	while(!kolejka.empty())
	{
        int y=kolejka.front();
        kolejka.pop();
        if(odw[y]==c)
            continue;
        odw[y]=c;
        for(int i=0;i<lista[y].size();i++)
        {
            int pom=lista[y][i];
            if(w[pom].kto!=c)
            {
                wynikk=1e9;
                break;
            }
            kolejka.push(kolor[w[pom].ojc]);
        }
        wynikk++;
	}
	wynik=min(wynik,wynikk);
	for(int child:w[c].Q)
		if(byl[child]==0)
            centroid(child);
}
int32_t main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int n,k,x,y;
    cin>>n>>k;
    w=new wi[n+3];
    for(int i=1;i<n;i++)
    {
        cin>>x>>y;
        w[x].Q.push_back(y);
        w[y].Q.push_back(x);
    }
    for(int i=1;i<=n;i++)
    {
        int c;
        cin>>c;
        kolor[i]=c;
        lista[c].push_back(i);
    }
    centroid(1);
    cout<<wynik-1;
    return 0;
}

Compilation message (stderr)

capital_city.cpp: In function 'void centroid(long long int)':
capital_city.cpp:63:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for(int i=0;i<lista[y].size();i++)
      |                     ~^~~~~~~~~~~~~~~~

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