oj.uz

Submission #235757

# Submission time Handle Problem Language Result Execution time Memory
235757 2020-05-29T15:52:19 Z rajarshi_basu Capital City (JOI20_capital_city) C++14
100 / 100
 1195 ms 37368 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <queue>
#include <deque>
#include <iomanip>
#include <list>
#include <cmath>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long 
//#define int long long
#define ld long double
#define vi vector<ll>
#define pb push_back
#define ff first
#define ss second
#define ii pair<int,int>
#define iii pair<int,ii>
#define il pair<ll,ll>
#define vv vector
#define endl '\n'

using namespace std;

const int MAXN = 200*100*10 + 5;
const ll INF = 1e15;


vi g[MAXN];
int color[MAXN];

int substree[MAXN];
int blocked[MAXN];

vi colorNodes[MAXN];
int parent[MAXN];

bool usedColors[MAXN];

queue<int> centroidQ;

void dfsSetup(int node,int p=-1){
	substree[node] = 1;
	parent[node] = p;
	usedColors[color[node]] = 0;
	for(auto e : g[node]){
		if(e != p and !blocked[e]){
			dfsSetup(e,node);
			substree[node] += substree[e];
		}
	}
}

void dfsDestroy(int node,int p = -1){
	substree[node] = -1;
	for(auto e : g[node]){
		if(e == p or blocked[e])continue;
		dfsDestroy(e,node);
	}
}

int getCentroid(int node,int tot,int p=-1){
	for(auto e: g[node]){
		if(e == p or blocked[e])continue;
		if(substree[e]*2 > tot)return getCentroid(e,tot,node);
	}
	return node;
}
int ans = MAXN;
void processTree(int root){
	dfsSetup(root);
	int c = getCentroid(root,substree[root]);
	dfsSetup(c);
	queue<int> currentColors;
	currentColors.push(color[c]);
	usedColors[color[c]] = 1;	

	int ctr = 0;
	bool bad = 0;
	while(!currentColors.empty()){
		int cc = currentColors.front();
		currentColors.pop();
		ctr++;
		for(auto e : colorNodes[cc]){
			if(substree[e] == -1 or blocked[e]){
				bad = 1;
				break;
			}else if(parent[e] != -1){
				if(!usedColors[color[parent[e]]]){
					currentColors.push(color[parent[e]]);
					usedColors[color[parent[e]]] = 1;
				}
			}
		}
		if(bad)break;
	}
	//cout << ": " << c << " " << bad << " " << ctr << endl;
	if(!bad){
		ans = min(ans,ctr-1);
	}

	for(auto e : g[c])if(!blocked[e])centroidQ.push(e);
	dfsDestroy(root);
	blocked[c] = 1;
}

void centroidDecomp(){
	centroidQ.push(0);
	while(!centroidQ.empty()){
		int item = centroidQ.front();
		centroidQ.pop();
		processTree(item);
		
	}
}


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

	int n,k;
	
	cin >> n >> k;
	ans = k-1;
	FOR(i,n-1){
		int a,b;
		cin >> a >> b;
		a--;b--;
		g[a].pb(b);
		g[b].pb(a);
	}
	FOR(i,n)cin >> color[i];
	FOR(i,n)colorNodes[color[i]].pb(i);

	centroidDecomp();
	cout << ans << endl;
	return 0;
}

Subtask #1
1.0 / 1.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 10 ms 9728 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Correct 10 ms 9728 KB Output is correct
8 Correct 10 ms 9728 KB Output is correct
9 Correct 10 ms 9728 KB Output is correct
10 Correct 10 ms 9728 KB Output is correct
11 Correct 13 ms 9856 KB Output is correct
12 Correct 12 ms 9984 KB Output is correct
13 Correct 12 ms 9984 KB Output is correct
14 Correct 12 ms 9856 KB Output is correct
15 Correct 16 ms 9984 KB Output is correct
16 Correct 12 ms 9984 KB Output is correct
17 Correct 12 ms 9984 KB Output is correct
18 Correct 12 ms 9984 KB Output is correct
19 Correct 12 ms 9984 KB Output is correct
20 Correct 11 ms 9984 KB Output is correct
21 Correct 12 ms 9984 KB Output is correct
22 Correct 12 ms 10112 KB Output is correct
23 Correct 12 ms 9984 KB Output is correct
24 Correct 12 ms 9984 KB Output is correct
25 Correct 12 ms 9984 KB Output is correct
26 Correct 13 ms 9984 KB Output is correct
27 Correct 13 ms 9984 KB Output is correct
28 Correct 12 ms 9984 KB Output is correct
29 Correct 12 ms 9984 KB Output is correct
30 Correct 12 ms 9984 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 969 ms 34784 KB Output is correct
2 Correct 265 ms 36888 KB Output is correct
3 Correct 987 ms 36352 KB Output is correct
4 Correct 272 ms 36856 KB Output is correct
5 Correct 912 ms 34172 KB Output is correct
6 Correct 263 ms 37176 KB Output is correct
7 Correct 930 ms 34464 KB Output is correct
8 Correct 267 ms 36876 KB Output is correct
9 Correct 1182 ms 33236 KB Output is correct
10 Correct 1080 ms 30940 KB Output is correct
11 Correct 1085 ms 33588 KB Output is correct
12 Correct 1119 ms 35576 KB Output is correct
13 Correct 1160 ms 30840 KB Output is correct
14 Correct 1136 ms 35960 KB Output is correct
15 Correct 1195 ms 35704 KB Output is correct
16 Correct 1078 ms 31608 KB Output is correct
17 Correct 1111 ms 32192 KB Output is correct
18 Correct 1185 ms 32248 KB Output is correct
19 Correct 1158 ms 34716 KB Output is correct
20 Correct 1142 ms 36440 KB Output is correct
21 Correct 10 ms 9728 KB Output is correct

Subtask #4
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 10 ms 9728 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Correct 10 ms 9728 KB Output is correct
8 Correct 10 ms 9728 KB Output is correct
9 Correct 10 ms 9728 KB Output is correct
10 Correct 10 ms 9728 KB Output is correct
11 Correct 13 ms 9856 KB Output is correct
12 Correct 12 ms 9984 KB Output is correct
13 Correct 12 ms 9984 KB Output is correct
14 Correct 12 ms 9856 KB Output is correct
15 Correct 16 ms 9984 KB Output is correct
16 Correct 12 ms 9984 KB Output is correct
17 Correct 12 ms 9984 KB Output is correct
18 Correct 12 ms 9984 KB Output is correct
19 Correct 12 ms 9984 KB Output is correct
20 Correct 11 ms 9984 KB Output is correct
21 Correct 12 ms 9984 KB Output is correct
22 Correct 12 ms 10112 KB Output is correct
23 Correct 12 ms 9984 KB Output is correct
24 Correct 12 ms 9984 KB Output is correct
25 Correct 12 ms 9984 KB Output is correct
26 Correct 13 ms 9984 KB Output is correct
27 Correct 13 ms 9984 KB Output is correct
28 Correct 12 ms 9984 KB Output is correct
29 Correct 12 ms 9984 KB Output is correct
30 Correct 12 ms 9984 KB Output is correct
31 Correct 969 ms 34784 KB Output is correct
32 Correct 265 ms 36888 KB Output is correct
33 Correct 987 ms 36352 KB Output is correct
34 Correct 272 ms 36856 KB Output is correct
35 Correct 912 ms 34172 KB Output is correct
36 Correct 263 ms 37176 KB Output is correct
37 Correct 930 ms 34464 KB Output is correct
38 Correct 267 ms 36876 KB Output is correct
39 Correct 1182 ms 33236 KB Output is correct
40 Correct 1080 ms 30940 KB Output is correct
41 Correct 1085 ms 33588 KB Output is correct
42 Correct 1119 ms 35576 KB Output is correct
43 Correct 1160 ms 30840 KB Output is correct
44 Correct 1136 ms 35960 KB Output is correct
45 Correct 1195 ms 35704 KB Output is correct
46 Correct 1078 ms 31608 KB Output is correct
47 Correct 1111 ms 32192 KB Output is correct
48 Correct 1185 ms 32248 KB Output is correct
49 Correct 1158 ms 34716 KB Output is correct
50 Correct 1142 ms 36440 KB Output is correct
51 Correct 10 ms 9728 KB Output is correct
52 Correct 756 ms 25368 KB Output is correct
53 Correct 782 ms 25376 KB Output is correct
54 Correct 852 ms 25464 KB Output is correct
55 Correct 825 ms 25444 KB Output is correct
56 Correct 779 ms 25464 KB Output is correct
57 Correct 772 ms 25340 KB Output is correct
58 Correct 741 ms 28328 KB Output is correct
59 Correct 715 ms 28536 KB Output is correct
60 Correct 889 ms 27396 KB Output is correct
61 Correct 1020 ms 27128 KB Output is correct
62 Correct 266 ms 37112 KB Output is correct
63 Correct 267 ms 37368 KB Output is correct
64 Correct 264 ms 36856 KB Output is correct
65 Correct 257 ms 37240 KB Output is correct
66 Correct 567 ms 30956 KB Output is correct
67 Correct 587 ms 30824 KB Output is correct
68 Correct 566 ms 30956 KB Output is correct
69 Correct 554 ms 30828 KB Output is correct
70 Correct 584 ms 30952 KB Output is correct
71 Correct 561 ms 31080 KB Output is correct
72 Correct 573 ms 31084 KB Output is correct
73 Correct 557 ms 30312 KB Output is correct
74 Correct 605 ms 30960 KB Output is correct
75 Correct 618 ms 30888 KB Output is correct
76 Correct 926 ms 30788 KB Output is correct
77 Correct 920 ms 29176 KB Output is correct
78 Correct 1077 ms 31860 KB Output is correct
79 Correct 1098 ms 30200 KB Output is correct
80 Correct 1119 ms 35980 KB Output is correct
81 Correct 1085 ms 33172 KB Output is correct
82 Correct 1123 ms 33272 KB Output is correct
83 Correct 1141 ms 30728 KB Output is correct
84 Correct 1094 ms 35192 KB Output is correct
85 Correct 1162 ms 34092 KB Output is correct
86 Correct 1056 ms 30036 KB Output is correct
87 Correct 1138 ms 31480 KB Output is correct
88 Correct 891 ms 33016 KB Output is correct
89 Correct 911 ms 29672 KB Output is correct
90 Correct 893 ms 29520 KB Output is correct
91 Correct 931 ms 31668 KB Output is correct
92 Correct 880 ms 30584 KB Output is correct
93 Correct 895 ms 30176 KB Output is correct
94 Correct 923 ms 29724 KB Output is correct
95 Correct 925 ms 30968 KB Output is correct
96 Correct 891 ms 29952 KB Output is correct
97 Correct 880 ms 31372 KB Output is correct