oj.uz

Submission #1014113

# Submission time Handle Problem Language Result Execution time Memory
1014113 2024-07-04T10:56:20 Z alexdd Capital City (JOI20_capital_city) C++17
1 / 100
 284 ms 34648 KB 
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n,k,rez=INF;
vector<int> con[200005];
int color[200005];
int fr[200005];
int siz[200005];
bool iss[200005];
void get_sizes(int nod, int par)
{
    siz[nod]=1;
    for(auto adj:con[nod])
    {
        if(adj!=par && !iss[adj])
        {
            get_sizes(adj,nod);
            siz[nod]+=siz[adj];
        }
    }
}
int get_centroid(int nod, int par, int tot)
{
    for(auto adj:con[nod])
        if(adj!=par && !iss[adj] && 2*siz[adj]>tot)
            return get_centroid(adj,nod,tot);
    return nod;
}
int cnt_color[200005];
void get_cnt_color(int nod, int par, int mycolor)
{
    cnt_color[nod]=0;
    if(color[nod]==mycolor) cnt_color[nod]++;
    for(auto adj:con[nod])
    {
        if(adj!=par && !iss[adj])
        {
            get_cnt_color(adj,nod,mycolor);
            cnt_color[nod] += cnt_color[adj];
        }
    }
}
int auxrez=0;
map<int,int> mp;
void get_rez(int nod, int par)
{
    mp[color[nod]]++;
    for(auto adj:con[nod])
        if(adj!=par && !iss[adj] && cnt_color[adj]>0)
            get_rez(adj,nod);
}
void centroid_decomposition(int c)
{
    get_sizes(c,-1);
    c = get_centroid(c,-1,siz[c]);

    get_cnt_color(c,-1,color[c]);
    if(cnt_color[c]==fr[color[c]])
    {
        mp.clear();
        get_rez(c,-1);
        rez = min(rez, (int)mp.size()-1);
    }

    iss[c]=1;
    for(auto adj:con[c])
        if(!iss[adj])
            centroid_decomposition(adj);
}
signed main()
{
    cin>>n>>k;
    int a,b;
    for(int i=1;i<n;i++)
    {
        cin>>a>>b;
        con[a].push_back(b);
        con[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
    {
        cin>>color[i];
        fr[color[i]]++;
    }
    centroid_decomposition(1);
    cout<<rez;
    return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6236 KB Output is correct
2 Correct 2 ms 6236 KB Output is correct
3 Correct 2 ms 6236 KB Output is correct
4 Correct 2 ms 6256 KB Output is correct
5 Correct 2 ms 6236 KB Output is correct
6 Correct 1 ms 6236 KB Output is correct
7 Correct 2 ms 6236 KB Output is correct
8 Correct 2 ms 6236 KB Output is correct
9 Correct 2 ms 6488 KB Output is correct
10 Correct 2 ms 6236 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6236 KB Output is correct
2 Correct 2 ms 6236 KB Output is correct
3 Correct 2 ms 6236 KB Output is correct
4 Correct 2 ms 6256 KB Output is correct
5 Correct 2 ms 6236 KB Output is correct
6 Correct 1 ms 6236 KB Output is correct
7 Correct 2 ms 6236 KB Output is correct
8 Correct 2 ms 6236 KB Output is correct
9 Correct 2 ms 6488 KB Output is correct
10 Correct 2 ms 6236 KB Output is correct
11 Incorrect 3 ms 6236 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 33364 KB Output is correct
2 Correct 165 ms 33820 KB Output is correct
3 Correct 235 ms 33020 KB Output is correct
4 Correct 155 ms 33936 KB Output is correct
5 Correct 240 ms 30548 KB Output is correct
6 Correct 156 ms 33888 KB Output is correct
7 Correct 245 ms 31316 KB Output is correct
8 Correct 162 ms 34648 KB Output is correct
9 Incorrect 284 ms 30548 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6236 KB Output is correct
2 Correct 2 ms 6236 KB Output is correct
3 Correct 2 ms 6236 KB Output is correct
4 Correct 2 ms 6256 KB Output is correct
5 Correct 2 ms 6236 KB Output is correct
6 Correct 1 ms 6236 KB Output is correct
7 Correct 2 ms 6236 KB Output is correct
8 Correct 2 ms 6236 KB Output is correct
9 Correct 2 ms 6488 KB Output is correct
10 Correct 2 ms 6236 KB Output is correct
11 Incorrect 3 ms 6236 KB Output isn't correct
12 Halted 0 ms 0 KB -