Submission #330103

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
330103	2020-11-23T23:16:41 Z	limabeans	Capital City (JOI20_capital_city)	C++17	100 / 100	782 ms	79596 KB

capital_city

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;




int n, k;
vector<int> g[maxn];
int c[maxn];
vector<int> C[maxn];


int ans = 1e9;


bool viz[maxn];



int siz[maxn];


void dfs1(int at, int p) {
    siz[at]=1;
    for (int to: g[at]) {
	if (viz[to]) continue;
	if (to==p) continue;
	dfs1(to,at);
	siz[at]+=siz[to];
    }
}

int findCenter(int at) {
    dfs1(at,-1);
    int S = siz[at];
    while (true) {
	int nxt = -1;
	for (int to: g[at]) {
	    if (viz[to]) continue;
	    if (siz[to]>siz[at]) continue;
	    if (siz[to]*2 >= S) {
		nxt = to;
		break;
	    }
	}
	if (nxt==-1) break;
	at=nxt;
    }

    return at;
}


int par[maxn];
int center[maxn];

void dfs2(int at, int p, int cent) {
    par[at] = p;
    center[at] = cent;
    for (int to: g[at]) {
	if (viz[to]) continue;
	if (to==p) continue;
	dfs2(to,at,cent);
    }
}

bool vizcol[maxn];

void solve(int at) {

    int At = findCenter(at);
    dfs2(At,At,At);



    
    bool ok = true;
    queue<int> qq;
    vector<int> res;
    int cnt = -1;
    qq.push(At);
    
    
    while (ok && !qq.empty()) {
	int at = qq.front();
	++cnt;
	qq.pop();

	while (ok) {
	    if (center[at]==0) break;

	    if (!vizcol[c[at]]) {
		cnt -= C[c[at]].size();
		vizcol[c[at]] = true;
		res.push_back(c[at]);
		for (int to: C[c[at]]) {
		    qq.push(to);
		    if (center[to]!=At) {
			ok = false;
			break;
		    }
		}
	    }
	    
	    center[at]=0;
	    at = par[at];
	    if (at==At) break;
	}
    }

    for (int cc: res) {
	vizcol[cc] = false;
    }

    if (cnt==0) {
	ans = min(ans, (int)res.size());
    }
    
    viz[At] = true;
    
    for (int to: g[At]) {
	if (!viz[to]) {
	    solve(to);
	}
    }
}

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

    cin>>n>>k;
    for (int i=0; i<n-1; i++) {
	int u,v; cin>>u>>v;
	g[u].push_back(v);
	g[v].push_back(u);
    }

    for (int i=1; i<=n; i++) {
	cin>>c[i];
	C[c[i]].push_back(i);
    }


    solve(1);

    cout<<ans-1<<endl;    
    return 0;
}

Subtask #1
1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	47468 KB	Output is correct
2	Correct	30 ms	47340 KB	Output is correct
3	Correct	30 ms	47340 KB	Output is correct
4	Correct	30 ms	47352 KB	Output is correct
5	Correct	29 ms	47340 KB	Output is correct
6	Correct	29 ms	47360 KB	Output is correct
7	Correct	29 ms	47340 KB	Output is correct
8	Correct	30 ms	47268 KB	Output is correct
9	Correct	30 ms	47340 KB	Output is correct
10	Correct	31 ms	47488 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	47468 KB	Output is correct
2	Correct	30 ms	47340 KB	Output is correct
3	Correct	30 ms	47340 KB	Output is correct
4	Correct	30 ms	47352 KB	Output is correct
5	Correct	29 ms	47340 KB	Output is correct
6	Correct	29 ms	47360 KB	Output is correct
7	Correct	29 ms	47340 KB	Output is correct
8	Correct	30 ms	47268 KB	Output is correct
9	Correct	30 ms	47340 KB	Output is correct
10	Correct	31 ms	47488 KB	Output is correct
11	Correct	31 ms	47468 KB	Output is correct
12	Correct	31 ms	47468 KB	Output is correct
13	Correct	32 ms	47468 KB	Output is correct
14	Correct	33 ms	47468 KB	Output is correct
15	Correct	32 ms	47616 KB	Output is correct
16	Correct	32 ms	47468 KB	Output is correct
17	Correct	32 ms	47596 KB	Output is correct
18	Correct	32 ms	47616 KB	Output is correct
19	Correct	33 ms	47596 KB	Output is correct
20	Correct	31 ms	47596 KB	Output is correct
21	Correct	32 ms	47596 KB	Output is correct
22	Correct	32 ms	47724 KB	Output is correct
23	Correct	33 ms	47616 KB	Output is correct
24	Correct	32 ms	47596 KB	Output is correct
25	Correct	32 ms	47596 KB	Output is correct
26	Correct	32 ms	47596 KB	Output is correct
27	Correct	32 ms	47596 KB	Output is correct
28	Correct	32 ms	47596 KB	Output is correct
29	Correct	32 ms	47596 KB	Output is correct
30	Correct	32 ms	47596 KB	Output is correct

Subtask #3
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	681 ms	79080 KB	Output is correct
2	Correct	235 ms	79596 KB	Output is correct
3	Correct	650 ms	78700 KB	Output is correct
4	Correct	242 ms	79596 KB	Output is correct
5	Correct	643 ms	75812 KB	Output is correct
6	Correct	239 ms	79596 KB	Output is correct
7	Correct	653 ms	76268 KB	Output is correct
8	Correct	244 ms	79592 KB	Output is correct
9	Correct	742 ms	75172 KB	Output is correct
10	Correct	724 ms	72476 KB	Output is correct
11	Correct	728 ms	75404 KB	Output is correct
12	Correct	729 ms	78076 KB	Output is correct
13	Correct	727 ms	71968 KB	Output is correct
14	Correct	705 ms	78136 KB	Output is correct
15	Correct	750 ms	77996 KB	Output is correct
16	Correct	724 ms	73104 KB	Output is correct
17	Correct	729 ms	73492 KB	Output is correct
18	Correct	721 ms	73768 KB	Output is correct
19	Correct	727 ms	76844 KB	Output is correct
20	Correct	764 ms	79168 KB	Output is correct
21	Correct	29 ms	47340 KB	Output is correct

Subtask #4
59.0 / 59.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	47468 KB	Output is correct
2	Correct	30 ms	47340 KB	Output is correct
3	Correct	30 ms	47340 KB	Output is correct
4	Correct	30 ms	47352 KB	Output is correct
5	Correct	29 ms	47340 KB	Output is correct
6	Correct	29 ms	47360 KB	Output is correct
7	Correct	29 ms	47340 KB	Output is correct
8	Correct	30 ms	47268 KB	Output is correct
9	Correct	30 ms	47340 KB	Output is correct
10	Correct	31 ms	47488 KB	Output is correct
11	Correct	31 ms	47468 KB	Output is correct
12	Correct	31 ms	47468 KB	Output is correct
13	Correct	32 ms	47468 KB	Output is correct
14	Correct	33 ms	47468 KB	Output is correct
15	Correct	32 ms	47616 KB	Output is correct
16	Correct	32 ms	47468 KB	Output is correct
17	Correct	32 ms	47596 KB	Output is correct
18	Correct	32 ms	47616 KB	Output is correct
19	Correct	33 ms	47596 KB	Output is correct
20	Correct	31 ms	47596 KB	Output is correct
21	Correct	32 ms	47596 KB	Output is correct
22	Correct	32 ms	47724 KB	Output is correct
23	Correct	33 ms	47616 KB	Output is correct
24	Correct	32 ms	47596 KB	Output is correct
25	Correct	32 ms	47596 KB	Output is correct
26	Correct	32 ms	47596 KB	Output is correct
27	Correct	32 ms	47596 KB	Output is correct
28	Correct	32 ms	47596 KB	Output is correct
29	Correct	32 ms	47596 KB	Output is correct
30	Correct	32 ms	47596 KB	Output is correct
31	Correct	681 ms	79080 KB	Output is correct
32	Correct	235 ms	79596 KB	Output is correct
33	Correct	650 ms	78700 KB	Output is correct
34	Correct	242 ms	79596 KB	Output is correct
35	Correct	643 ms	75812 KB	Output is correct
36	Correct	239 ms	79596 KB	Output is correct
37	Correct	653 ms	76268 KB	Output is correct
38	Correct	244 ms	79592 KB	Output is correct
39	Correct	742 ms	75172 KB	Output is correct
40	Correct	724 ms	72476 KB	Output is correct
41	Correct	728 ms	75404 KB	Output is correct
42	Correct	729 ms	78076 KB	Output is correct
43	Correct	727 ms	71968 KB	Output is correct
44	Correct	705 ms	78136 KB	Output is correct
45	Correct	750 ms	77996 KB	Output is correct
46	Correct	724 ms	73104 KB	Output is correct
47	Correct	729 ms	73492 KB	Output is correct
48	Correct	721 ms	73768 KB	Output is correct
49	Correct	727 ms	76844 KB	Output is correct
50	Correct	764 ms	79168 KB	Output is correct
51	Correct	29 ms	47340 KB	Output is correct
52	Correct	559 ms	63052 KB	Output is correct
53	Correct	585 ms	62980 KB	Output is correct
54	Correct	602 ms	62976 KB	Output is correct
55	Correct	590 ms	62888 KB	Output is correct
56	Correct	588 ms	62892 KB	Output is correct
57	Correct	567 ms	63052 KB	Output is correct
58	Correct	509 ms	66284 KB	Output is correct
59	Correct	563 ms	66540 KB	Output is correct
60	Correct	678 ms	65772 KB	Output is correct
61	Correct	662 ms	65516 KB	Output is correct
62	Correct	262 ms	79468 KB	Output is correct
63	Correct	251 ms	79596 KB	Output is correct
64	Correct	239 ms	79468 KB	Output is correct
65	Correct	240 ms	79596 KB	Output is correct
66	Correct	434 ms	71268 KB	Output is correct
67	Correct	451 ms	71216 KB	Output is correct
68	Correct	484 ms	71444 KB	Output is correct
69	Correct	454 ms	71396 KB	Output is correct
70	Correct	466 ms	71396 KB	Output is correct
71	Correct	470 ms	71356 KB	Output is correct
72	Correct	458 ms	71268 KB	Output is correct
73	Correct	438 ms	70372 KB	Output is correct
74	Correct	468 ms	71384 KB	Output is correct
75	Correct	465 ms	71396 KB	Output is correct
76	Correct	659 ms	70148 KB	Output is correct
77	Correct	648 ms	68104 KB	Output is correct
78	Correct	723 ms	73640 KB	Output is correct
79	Correct	729 ms	71464 KB	Output is correct
80	Correct	732 ms	78372 KB	Output is correct
81	Correct	748 ms	75016 KB	Output is correct
82	Correct	748 ms	75040 KB	Output is correct
83	Correct	717 ms	71820 KB	Output is correct
84	Correct	749 ms	77616 KB	Output is correct
85	Correct	742 ms	76076 KB	Output is correct
86	Correct	717 ms	71404 KB	Output is correct
87	Correct	782 ms	73108 KB	Output is correct
88	Correct	623 ms	74220 KB	Output is correct
89	Correct	624 ms	70084 KB	Output is correct
90	Correct	617 ms	69996 KB	Output is correct
91	Correct	617 ms	72400 KB	Output is correct
92	Correct	613 ms	71148 KB	Output is correct
93	Correct	608 ms	70764 KB	Output is correct
94	Correct	619 ms	69996 KB	Output is correct
95	Correct	607 ms	71600 KB	Output is correct
96	Correct	618 ms	70288 KB	Output is correct
97	Correct	614 ms	72300 KB	Output is correct

Submission #330103

Compilation message

Subtask #1 1.0 / 1.0

Subtask #2 10.0 / 10.0

Subtask #3 30.0 / 30.0

Subtask #4 59.0 / 59.0

Subtask #1
1.0 / 1.0

Subtask #2
10.0 / 10.0

Subtask #3
30.0 / 30.0

Subtask #4
59.0 / 59.0