oj.uz

Submission #720262

# Submission time Handle Problem Language Result Execution time Memory
720262 2023-04-07T19:00:42 Z PoPularPlusPlus Capital City (JOI20_capital_city) C++17
100 / 100
 756 ms 41980 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007; 
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

bool remender(ll a , ll b){return a%b;}

//freopen("problemname.in", "r", stdin);
//freopen("problemname.out", "w", stdout);

const int N = 200002;
int n , k;
vector<int> adj[N];
int col[N];
bool vis[N],vis_col[N];
vector<int> v[N];
int sub[N];
int ans;
int p[N];
int done[N];

void pre(int node , int par){
	sub[node] = 1;
	for(int i : adj[node]){
		if(!vis[i] && i != par){
			pre(i , node);
			sub[node] += sub[i];
		}
	}
}

int find(int node , int par , int half){
	for(int i : adj[node]){
		if(!vis[i] && i != par && sub[i] > half){
			return find(i , node , half);
		}
	}
	return node;
}

int counting(int node , int par , int c , int centroid){
	p[node] = par;
	done[node] = centroid;
	int cnt = 0;
	for(int i : adj[node]){
		if(!vis[i] && i != par){
			cnt += counting(i , node , c , centroid);
		}
	}
	if(col[node] == c)cnt++;
	return cnt;
}

void dfs(int node , int par){
	done[node] = 0;
	for(int i : adj[node]){
		if(!vis[i] && i != par){
			dfs(i , node);
		}
	}
}

void centroid_decomposition(int node){
	pre(node , node);
	int centroid = find(node , node , sub[node]/2);
	int c = col[centroid];
	int cnt = counting(centroid,centroid,c ,-centroid);
	if(cnt == v[c].size()){
		int res = 0;
		queue<int> q;
		for(int i : v[c]){
			done[i] = 1;
			q.push(i);
		}
		while(q.size()){
			node = q.front();
			q.pop();
			if(node == centroid)continue;
			int par = p[node];
			if(done[v[col[par]][0]] == -centroid){
				if(vis_col[col[par]]){
					res = -1;
					break;
				}
				res++;
				for(int i : v[col[par]]){
					if(done[i] != -centroid){
						res = -1;
						break;
					}
					done[i] = 1;
					q.push(i);
				}
			}
			else if(done[v[col[par]][0]] == 0){
				res = -1;
				break;
			}
		}
		if(res != -1){
			ans = min(ans , res);
		}
	}
	dfs(centroid , centroid);
	vis_col[c] = 1;
	vis[centroid] = 1;
	for(int i : adj[centroid]){
		if(!vis[i]){
			centroid_decomposition(i);
		}
	}
}

void solve(){
	cin >> n;
	cin >> k;
	for(int i = 0; i < n-1; i++){
		int a , b;
		cin >> a >> b;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	for(int i = 1; i <= n; i++){
		cin >> col[i];
		v[col[i]].pb(i);
	}
	memset(vis,0,sizeof vis);
	memset(vis_col,0,sizeof vis_col);
	memset(done,0,sizeof done);
	ans = k-1;
	centroid_decomposition(1);
	cout << ans << '\n';
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
	//int t;cin >> t;while(t--)
	solve();
	return 0;
}

Compilation message

capital_city.cpp: In function 'void centroid_decomposition(int)':
capital_city.cpp:81:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |  if(cnt == v[c].size()){
      |     ~~~~^~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10836 KB Output is correct
2 Correct 7 ms 10884 KB Output is correct
3 Correct 8 ms 10880 KB Output is correct
4 Correct 9 ms 10888 KB Output is correct
5 Correct 9 ms 10836 KB Output is correct
6 Correct 8 ms 10888 KB Output is correct
7 Correct 8 ms 10884 KB Output is correct
8 Correct 9 ms 10912 KB Output is correct
9 Correct 8 ms 10836 KB Output is correct
10 Correct 9 ms 10880 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10836 KB Output is correct
2 Correct 7 ms 10884 KB Output is correct
3 Correct 8 ms 10880 KB Output is correct
4 Correct 9 ms 10888 KB Output is correct
5 Correct 9 ms 10836 KB Output is correct
6 Correct 8 ms 10888 KB Output is correct
7 Correct 8 ms 10884 KB Output is correct
8 Correct 9 ms 10912 KB Output is correct
9 Correct 8 ms 10836 KB Output is correct
10 Correct 9 ms 10880 KB Output is correct
11 Correct 11 ms 11020 KB Output is correct
12 Correct 15 ms 11040 KB Output is correct
13 Correct 11 ms 11024 KB Output is correct
14 Correct 11 ms 10940 KB Output is correct
15 Correct 9 ms 11064 KB Output is correct
16 Correct 8 ms 11020 KB Output is correct
17 Correct 9 ms 11020 KB Output is correct
18 Correct 8 ms 11092 KB Output is correct
19 Correct 8 ms 11024 KB Output is correct
20 Correct 8 ms 11092 KB Output is correct
21 Correct 7 ms 11092 KB Output is correct
22 Correct 10 ms 11208 KB Output is correct
23 Correct 8 ms 11092 KB Output is correct
24 Correct 9 ms 10964 KB Output is correct
25 Correct 9 ms 11108 KB Output is correct
26 Correct 8 ms 11092 KB Output is correct
27 Correct 8 ms 11092 KB Output is correct
28 Correct 8 ms 11120 KB Output is correct
29 Correct 8 ms 11016 KB Output is correct
30 Correct 8 ms 11024 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 522 ms 41440 KB Output is correct
2 Correct 225 ms 41872 KB Output is correct
3 Correct 542 ms 41128 KB Output is correct
4 Correct 188 ms 41880 KB Output is correct
5 Correct 536 ms 38180 KB Output is correct
6 Correct 184 ms 41980 KB Output is correct
7 Correct 533 ms 38436 KB Output is correct
8 Correct 212 ms 41544 KB Output is correct
9 Correct 668 ms 36828 KB Output is correct
10 Correct 633 ms 34456 KB Output is correct
11 Correct 628 ms 37196 KB Output is correct
12 Correct 661 ms 40036 KB Output is correct
13 Correct 638 ms 34052 KB Output is correct
14 Correct 588 ms 40332 KB Output is correct
15 Correct 685 ms 39824 KB Output is correct
16 Correct 655 ms 34920 KB Output is correct
17 Correct 676 ms 35548 KB Output is correct
18 Correct 708 ms 35648 KB Output is correct
19 Correct 631 ms 38836 KB Output is correct
20 Correct 634 ms 41164 KB Output is correct
21 Correct 6 ms 10836 KB Output is correct

Subtask #4
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10836 KB Output is correct
2 Correct 7 ms 10884 KB Output is correct
3 Correct 8 ms 10880 KB Output is correct
4 Correct 9 ms 10888 KB Output is correct
5 Correct 9 ms 10836 KB Output is correct
6 Correct 8 ms 10888 KB Output is correct
7 Correct 8 ms 10884 KB Output is correct
8 Correct 9 ms 10912 KB Output is correct
9 Correct 8 ms 10836 KB Output is correct
10 Correct 9 ms 10880 KB Output is correct
11 Correct 11 ms 11020 KB Output is correct
12 Correct 15 ms 11040 KB Output is correct
13 Correct 11 ms 11024 KB Output is correct
14 Correct 11 ms 10940 KB Output is correct
15 Correct 9 ms 11064 KB Output is correct
16 Correct 8 ms 11020 KB Output is correct
17 Correct 9 ms 11020 KB Output is correct
18 Correct 8 ms 11092 KB Output is correct
19 Correct 8 ms 11024 KB Output is correct
20 Correct 8 ms 11092 KB Output is correct
21 Correct 7 ms 11092 KB Output is correct
22 Correct 10 ms 11208 KB Output is correct
23 Correct 8 ms 11092 KB Output is correct
24 Correct 9 ms 10964 KB Output is correct
25 Correct 9 ms 11108 KB Output is correct
26 Correct 8 ms 11092 KB Output is correct
27 Correct 8 ms 11092 KB Output is correct
28 Correct 8 ms 11120 KB Output is correct
29 Correct 8 ms 11016 KB Output is correct
30 Correct 8 ms 11024 KB Output is correct
31 Correct 522 ms 41440 KB Output is correct
32 Correct 225 ms 41872 KB Output is correct
33 Correct 542 ms 41128 KB Output is correct
34 Correct 188 ms 41880 KB Output is correct
35 Correct 536 ms 38180 KB Output is correct
36 Correct 184 ms 41980 KB Output is correct
37 Correct 533 ms 38436 KB Output is correct
38 Correct 212 ms 41544 KB Output is correct
39 Correct 668 ms 36828 KB Output is correct
40 Correct 633 ms 34456 KB Output is correct
41 Correct 628 ms 37196 KB Output is correct
42 Correct 661 ms 40036 KB Output is correct
43 Correct 638 ms 34052 KB Output is correct
44 Correct 588 ms 40332 KB Output is correct
45 Correct 685 ms 39824 KB Output is correct
46 Correct 655 ms 34920 KB Output is correct
47 Correct 676 ms 35548 KB Output is correct
48 Correct 708 ms 35648 KB Output is correct
49 Correct 631 ms 38836 KB Output is correct
50 Correct 634 ms 41164 KB Output is correct
51 Correct 6 ms 10836 KB Output is correct
52 Correct 436 ms 25240 KB Output is correct
53 Correct 393 ms 25208 KB Output is correct
54 Correct 419 ms 25244 KB Output is correct
55 Correct 490 ms 25272 KB Output is correct
56 Correct 402 ms 25164 KB Output is correct
57 Correct 479 ms 25236 KB Output is correct
58 Correct 394 ms 28440 KB Output is correct
59 Correct 336 ms 28800 KB Output is correct
60 Correct 471 ms 28028 KB Output is correct
61 Correct 495 ms 27596 KB Output is correct
62 Correct 181 ms 41948 KB Output is correct
63 Correct 179 ms 41952 KB Output is correct
64 Correct 204 ms 41796 KB Output is correct
65 Correct 179 ms 41924 KB Output is correct
66 Correct 330 ms 33732 KB Output is correct
67 Correct 314 ms 33696 KB Output is correct
68 Correct 311 ms 33720 KB Output is correct
69 Correct 297 ms 33908 KB Output is correct
70 Correct 390 ms 33740 KB Output is correct
71 Correct 325 ms 33732 KB Output is correct
72 Correct 301 ms 33736 KB Output is correct
73 Correct 309 ms 32996 KB Output is correct
74 Correct 347 ms 33816 KB Output is correct
75 Correct 310 ms 33788 KB Output is correct
76 Correct 510 ms 31996 KB Output is correct
77 Correct 522 ms 30104 KB Output is correct
78 Correct 598 ms 35388 KB Output is correct
79 Correct 617 ms 33484 KB Output is correct
80 Correct 688 ms 40608 KB Output is correct
81 Correct 756 ms 37168 KB Output is correct
82 Correct 657 ms 37196 KB Output is correct
83 Correct 605 ms 33772 KB Output is correct
84 Correct 613 ms 39580 KB Output is correct
85 Correct 671 ms 38128 KB Output is correct
86 Correct 701 ms 33340 KB Output is correct
87 Correct 711 ms 35212 KB Output is correct
88 Correct 537 ms 36172 KB Output is correct
89 Correct 577 ms 32312 KB Output is correct
90 Correct 570 ms 32152 KB Output is correct
91 Correct 568 ms 34384 KB Output is correct
92 Correct 533 ms 33096 KB Output is correct
93 Correct 573 ms 32896 KB Output is correct
94 Correct 516 ms 32332 KB Output is correct
95 Correct 534 ms 33696 KB Output is correct
96 Correct 523 ms 32288 KB Output is correct
97 Correct 581 ms 34404 KB Output is correct