oj.uz

답안 #314291

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
314291 2020-10-19T12:59:18 Z vipghn2003 수도 (JOI20_capital_city) C++14
100 / 100
 1038 ms 36712 KB 
#include<bits/stdc++.h>

using namespace std;

const int N=2e5+5;
int n,k,c[N],cnt[N],res,sz[N],par[N],num[N];
vector<int>adj[N],col[N],vec;
bool cenvis[N],colvis[N],vis[N];

void findsz(int u,int p=-1)
{
	sz[u]=1;
	for(auto&v:adj[u])
    {
		if (v!=p&&!cenvis[v])
		{
			findsz(v,u);
			sz[u]+=sz[v];
		}
	}
}

int find_cen(int u,int p,int m)
{
	for(auto&v:adj[u])
	{
		if(v!=p&&!cenvis[v])
        {
			if (sz[v]>m/2) return find_cen(v,u,m);
		}
	}
	return u;
}

void prep(int u,int p)
{
    vec.push_back(c[u]);
    num[c[u]]=0;
    par[u]=p;
    col[c[u]].push_back(u);
    vis[u]=false;
    colvis[c[u]]=false;
    for(auto&v:adj[u])
    {
        if(v!=p&&!cenvis[v]) prep(v,u);
    }
}

void centroid(int root=1,int p=-1)
{
    findsz(root,root);
	int u=find_cen(root,root,sz[root]);
	prep(u,u);
    queue<int>pq;
    pq.push(c[u]);
    colvis[c[u]]=true;
    int op=0;
    while(!pq.empty())
    {
        int color=pq.front();
        pq.pop();
        op++;
        for(auto&x:col[color])
        {
            while(!vis[x])
            {
                if(!colvis[c[x]]) pq.push(c[x]);
                vis[x]=true;
                colvis[c[x]]=true;
                num[c[x]]++;
                x=par[x];
            }
        }
    }
    bool kt=true;
    while(!vec.empty())
    {
        int color=vec.back();
        col[color].clear();
        vec.pop_back();
        if(colvis[color]&&num[color]!=cnt[color]) kt=false;
    }
    if(kt) res=min(res,op-1);
	cenvis[u]=true;
	for(auto&v:adj[u]) if(!cenvis[v]) centroid(v,u);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    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>>c[i];
        cnt[c[i]]++;
    }
    res=1e9;
    centroid(1);
    cout<<res;
}

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9856 KB Output is correct
2 Correct 6 ms 9728 KB Output is correct
3 Correct 7 ms 9728 KB Output is correct
4 Correct 7 ms 9728 KB Output is correct
5 Correct 7 ms 9728 KB Output is correct
6 Correct 6 ms 9728 KB Output is correct
7 Correct 6 ms 9728 KB Output is correct
8 Correct 6 ms 9728 KB Output is correct
9 Correct 7 ms 9728 KB Output is correct
10 Correct 6 ms 9728 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9856 KB Output is correct
2 Correct 6 ms 9728 KB Output is correct
3 Correct 7 ms 9728 KB Output is correct
4 Correct 7 ms 9728 KB Output is correct
5 Correct 7 ms 9728 KB Output is correct
6 Correct 6 ms 9728 KB Output is correct
7 Correct 6 ms 9728 KB Output is correct
8 Correct 6 ms 9728 KB Output is correct
9 Correct 7 ms 9728 KB Output is correct
10 Correct 6 ms 9728 KB Output is correct
11 Correct 9 ms 9856 KB Output is correct
12 Correct 9 ms 9984 KB Output is correct
13 Correct 9 ms 9856 KB Output is correct
14 Correct 9 ms 9856 KB Output is correct
15 Correct 9 ms 9984 KB Output is correct
16 Correct 9 ms 9984 KB Output is correct
17 Correct 8 ms 9984 KB Output is correct
18 Correct 8 ms 9984 KB Output is correct
19 Correct 8 ms 9984 KB Output is correct
20 Correct 8 ms 9984 KB Output is correct
21 Correct 8 ms 9984 KB Output is correct
22 Correct 10 ms 9984 KB Output is correct
23 Correct 9 ms 9984 KB Output is correct
24 Correct 9 ms 9984 KB Output is correct
25 Correct 9 ms 9984 KB Output is correct
26 Correct 10 ms 9984 KB Output is correct
27 Correct 10 ms 9984 KB Output is correct
28 Correct 9 ms 10144 KB Output is correct
29 Correct 11 ms 9984 KB Output is correct
30 Correct 9 ms 9984 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 935 ms 36336 KB Output is correct
2 Correct 265 ms 36588 KB Output is correct
3 Correct 892 ms 36208 KB Output is correct
4 Correct 272 ms 36664 KB Output is correct
5 Correct 890 ms 34288 KB Output is correct
6 Correct 262 ms 36656 KB Output is correct
7 Correct 884 ms 34288 KB Output is correct
8 Correct 260 ms 36200 KB Output is correct
9 Correct 1004 ms 32748 KB Output is correct
10 Correct 990 ms 31208 KB Output is correct
11 Correct 1006 ms 32952 KB Output is correct
12 Correct 1000 ms 34668 KB Output is correct
13 Correct 984 ms 30956 KB Output is correct
14 Correct 992 ms 34692 KB Output is correct
15 Correct 1004 ms 34540 KB Output is correct
16 Correct 992 ms 31592 KB Output is correct
17 Correct 988 ms 31852 KB Output is correct
18 Correct 987 ms 31976 KB Output is correct
19 Correct 995 ms 33896 KB Output is correct
20 Correct 1010 ms 35200 KB Output is correct
21 Correct 7 ms 9728 KB Output is correct

Subtask #4
59.0 / 59.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9856 KB Output is correct
2 Correct 6 ms 9728 KB Output is correct
3 Correct 7 ms 9728 KB Output is correct
4 Correct 7 ms 9728 KB Output is correct
5 Correct 7 ms 9728 KB Output is correct
6 Correct 6 ms 9728 KB Output is correct
7 Correct 6 ms 9728 KB Output is correct
8 Correct 6 ms 9728 KB Output is correct
9 Correct 7 ms 9728 KB Output is correct
10 Correct 6 ms 9728 KB Output is correct
11 Correct 9 ms 9856 KB Output is correct
12 Correct 9 ms 9984 KB Output is correct
13 Correct 9 ms 9856 KB Output is correct
14 Correct 9 ms 9856 KB Output is correct
15 Correct 9 ms 9984 KB Output is correct
16 Correct 9 ms 9984 KB Output is correct
17 Correct 8 ms 9984 KB Output is correct
18 Correct 8 ms 9984 KB Output is correct
19 Correct 8 ms 9984 KB Output is correct
20 Correct 8 ms 9984 KB Output is correct
21 Correct 8 ms 9984 KB Output is correct
22 Correct 10 ms 9984 KB Output is correct
23 Correct 9 ms 9984 KB Output is correct
24 Correct 9 ms 9984 KB Output is correct
25 Correct 9 ms 9984 KB Output is correct
26 Correct 10 ms 9984 KB Output is correct
27 Correct 10 ms 9984 KB Output is correct
28 Correct 9 ms 10144 KB Output is correct
29 Correct 11 ms 9984 KB Output is correct
30 Correct 9 ms 9984 KB Output is correct
31 Correct 935 ms 36336 KB Output is correct
32 Correct 265 ms 36588 KB Output is correct
33 Correct 892 ms 36208 KB Output is correct
34 Correct 272 ms 36664 KB Output is correct
35 Correct 890 ms 34288 KB Output is correct
36 Correct 262 ms 36656 KB Output is correct
37 Correct 884 ms 34288 KB Output is correct
38 Correct 260 ms 36200 KB Output is correct
39 Correct 1004 ms 32748 KB Output is correct
40 Correct 990 ms 31208 KB Output is correct
41 Correct 1006 ms 32952 KB Output is correct
42 Correct 1000 ms 34668 KB Output is correct
43 Correct 984 ms 30956 KB Output is correct
44 Correct 992 ms 34692 KB Output is correct
45 Correct 1004 ms 34540 KB Output is correct
46 Correct 992 ms 31592 KB Output is correct
47 Correct 988 ms 31852 KB Output is correct
48 Correct 987 ms 31976 KB Output is correct
49 Correct 995 ms 33896 KB Output is correct
50 Correct 1010 ms 35200 KB Output is correct
51 Correct 7 ms 9728 KB Output is correct
52 Correct 609 ms 25008 KB Output is correct
53 Correct 676 ms 25068 KB Output is correct
54 Correct 654 ms 24940 KB Output is correct
55 Correct 666 ms 25064 KB Output is correct
56 Correct 655 ms 25068 KB Output is correct
57 Correct 646 ms 24940 KB Output is correct
58 Correct 692 ms 28136 KB Output is correct
59 Correct 658 ms 28136 KB Output is correct
60 Correct 829 ms 28140 KB Output is correct
61 Correct 886 ms 27880 KB Output is correct
62 Correct 266 ms 36576 KB Output is correct
63 Correct 271 ms 36712 KB Output is correct
64 Correct 270 ms 36332 KB Output is correct
65 Correct 268 ms 36672 KB Output is correct
66 Correct 476 ms 31084 KB Output is correct
67 Correct 487 ms 31220 KB Output is correct
68 Correct 473 ms 31088 KB Output is correct
69 Correct 496 ms 31084 KB Output is correct
70 Correct 519 ms 31084 KB Output is correct
71 Correct 487 ms 31052 KB Output is correct
72 Correct 486 ms 31084 KB Output is correct
73 Correct 492 ms 30572 KB Output is correct
74 Correct 489 ms 31212 KB Output is correct
75 Correct 494 ms 31084 KB Output is correct
76 Correct 787 ms 30572 KB Output is correct
77 Correct 757 ms 29548 KB Output is correct
78 Correct 1033 ms 31724 KB Output is correct
79 Correct 1002 ms 30572 KB Output is correct
80 Correct 996 ms 34792 KB Output is correct
81 Correct 1018 ms 32932 KB Output is correct
82 Correct 1038 ms 33004 KB Output is correct
83 Correct 1028 ms 30824 KB Output is correct
84 Correct 1033 ms 34460 KB Output is correct
85 Correct 1020 ms 33512 KB Output is correct
86 Correct 1018 ms 30572 KB Output is correct
87 Correct 1002 ms 31600 KB Output is correct
88 Correct 895 ms 32360 KB Output is correct
89 Correct 853 ms 29928 KB Output is correct
90 Correct 852 ms 29804 KB Output is correct
91 Correct 842 ms 31212 KB Output is correct
92 Correct 851 ms 30568 KB Output is correct
93 Correct 848 ms 30316 KB Output is correct
94 Correct 847 ms 29932 KB Output is correct
95 Correct 863 ms 30828 KB Output is correct
96 Correct 864 ms 30184 KB Output is correct
97 Correct 853 ms 31336 KB Output is correct