oj.uz

Submission #414938

# Submission time Handle Problem Language Result Execution time Memory
414938 2021-05-31T10:49:14 Z Pro_ktmr Capital City (JOI20_capital_city) C++17
100 / 100
 2840 ms 97124 KB 
#pragma GCC target ("avx")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3")

#include"bits/stdc++.h"
#include<unordered_set>
#include<unordered_map>
#include<random>
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
int dx[4]={ 1,0,-1,0 };
int dy[4]={ 0,1,0,-1 };

int N, K;
vector<int> e[200000];
int C[200000];

int G[200000] ={};
bool used[200000] ={};

int sub[200000];
int par[200000];
vector<int> chi[200000];
bool ok[200000];
int dfs(int n, int p, int N){
	sub[n] = 1;
	par[n] = p;
	chi[n].clear();
	ok[n] = true;
	rep(i, e[n].size()){
		if(e[n][i] == p || used[e[n][i]]) continue;
		chi[n].pb(e[n][i]);
		int ret = dfs(e[n][i], n, N);
		if(ret > N/2) ok[n] = false;
		sub[n] += ret;
	}
	if(N-sub[n] > N/2) ok[n] = false;
	return sub[n];
}

int ans = 200000;
void DivideAndConquer(vector<int> v){
	unordered_map<int, vector<int>> g;
	rep(i, v.size()){
		g[C[v[i]]].pb(v[i]);
	}

	dfs(v[0], -1, v.size());
	int m = -1;
	rep(i, v.size()){
		if(ok[v[i]]) m = v[i];
	}
	dfs(m, -1, v.size());

	unordered_set<int> group;
	queue<int> que;
	unordered_set<int> vis;
	if(g[C[m]].size() != G[C[m]]) goto NEXT;
	rep(i, g[C[m]].size()) que.push(g[C[m]][i]);
	group.insert(C[m]);
	vis.insert(m);
	while(!que.empty()){
		int a = que.front();
		que.pop();
		while(m != a){
			a = par[a];
			if(vis.count(a)) break;
			vis.insert(a);
			if(group.count(C[a])) continue;
			if(g[C[a]].size() != G[C[a]]) goto NEXT;
			rep(i, g[C[a]].size()){
				que.push(g[C[a]][i]);
				vis.insert(g[C[a]][i]);
			}
			group.insert(C[a]);
		}
	}

	ans = min(ans, (int)group.size()-1);

NEXT:

	used[m] = true;
	unordered_set<int> st;
	st.insert(m);
	vector<int> nxt;
	rep(i, v.size()){
		if(st.count(v[i])) continue;
		nxt.clear();
		queue<int> q;
		q.push(v[i]);
		while(!q.empty()){
			int n = q.front();
			q.pop();
			nxt.pb(n);
			st.insert(n);
			rep(j, e[n].size()){
				if(st.count(e[n][j]) || used[e[n][j]]) continue;
				q.push(e[n][j]);
			}
		}
		DivideAndConquer(nxt);
	}
}

signed main(){
	scanf("%d%d", &N, &K);
	rep(i, N-1){
		int A, B; scanf("%d%d", &A, &B); A--; B--;
		e[A].pb(B);
		e[B].pb(A);
	}
	rep(i, N){
		scanf("%d", C+i); C[i]--;
		G[C[i]]++;
	}

	vector<int> v;
	rep(i, N) v.pb(i);
	DivideAndConquer(v);
	printf("%d\n", ans);
}

Compilation message

capital_city.cpp: In function 'int dfs(int, int, int)':
capital_city.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
capital_city.cpp:35:2: note: in expansion of macro 'rep'
   35 |  rep(i, e[n].size()){
      |  ^~~
capital_city.cpp: In function 'void DivideAndConquer(std::vector<int>)':
capital_city.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
capital_city.cpp:49:2: note: in expansion of macro 'rep'
   49 |  rep(i, v.size()){
      |  ^~~
capital_city.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
capital_city.cpp:55:2: note: in expansion of macro 'rep'
   55 |  rep(i, v.size()){
      |  ^~~
capital_city.cpp:63:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |  if(g[C[m]].size() != G[C[m]]) goto NEXT;
      |     ~~~~~~~~~~~~~~~^~~~~~~~~~
capital_city.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
capital_city.cpp:64:2: note: in expansion of macro 'rep'
   64 |  rep(i, g[C[m]].size()) que.push(g[C[m]][i]);
      |  ^~~
capital_city.cpp:75:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   75 |    if(g[C[a]].size() != G[C[a]]) goto NEXT;
      |       ~~~~~~~~~~~~~~~^~~~~~~~~~
capital_city.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
capital_city.cpp:76:4: note: in expansion of macro 'rep'
   76 |    rep(i, g[C[a]].size()){
      |    ^~~
capital_city.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
capital_city.cpp:92:2: note: in expansion of macro 'rep'
   92 |  rep(i, v.size()){
      |  ^~~
capital_city.cpp:15:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
capital_city.cpp:102:4: note: in expansion of macro 'rep'
  102 |    rep(j, e[n].size()){
      |    ^~~
capital_city.cpp: In function 'int main()':
capital_city.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
capital_city.cpp:113:2: note: in expansion of macro 'rep'
  113 |  rep(i, N-1){
      |  ^~~
capital_city.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
capital_city.cpp:118:2: note: in expansion of macro 'rep'
  118 |  rep(i, N){
      |  ^~~
capital_city.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
capital_city.cpp:124:2: note: in expansion of macro 'rep'
  124 |  rep(i, N) v.pb(i);
      |  ^~~
capital_city.cpp:112:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |  scanf("%d%d", &N, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~
capital_city.cpp:114:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |   int A, B; scanf("%d%d", &A, &B); A--; B--;
      |             ~~~~~^~~~~~~~~~~~~~~~
capital_city.cpp:119:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |   scanf("%d", C+i); C[i]--;
      |   ~~~~~^~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 8 ms 9700 KB Output is correct
4 Correct 7 ms 9676 KB Output is correct
5 Correct 7 ms 9704 KB Output is correct
6 Correct 7 ms 9724 KB Output is correct
7 Correct 7 ms 9676 KB Output is correct
8 Correct 7 ms 9640 KB Output is correct
9 Correct 7 ms 9676 KB Output is correct
10 Correct 7 ms 9700 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 8 ms 9700 KB Output is correct
4 Correct 7 ms 9676 KB Output is correct
5 Correct 7 ms 9704 KB Output is correct
6 Correct 7 ms 9724 KB Output is correct
7 Correct 7 ms 9676 KB Output is correct
8 Correct 7 ms 9640 KB Output is correct
9 Correct 7 ms 9676 KB Output is correct
10 Correct 7 ms 9700 KB Output is correct
11 Correct 14 ms 10188 KB Output is correct
12 Correct 14 ms 10096 KB Output is correct
13 Correct 13 ms 10124 KB Output is correct
14 Correct 15 ms 10088 KB Output is correct
15 Correct 17 ms 10336 KB Output is correct
16 Correct 16 ms 10284 KB Output is correct
17 Correct 12 ms 10224 KB Output is correct
18 Correct 13 ms 10320 KB Output is correct
19 Correct 14 ms 10316 KB Output is correct
20 Correct 14 ms 10188 KB Output is correct
21 Correct 14 ms 10316 KB Output is correct
22 Correct 15 ms 10540 KB Output is correct
23 Correct 17 ms 10436 KB Output is correct
24 Correct 17 ms 10348 KB Output is correct
25 Correct 17 ms 10436 KB Output is correct
26 Correct 18 ms 10404 KB Output is correct
27 Correct 17 ms 10316 KB Output is correct
28 Correct 18 ms 10348 KB Output is correct
29 Correct 17 ms 10416 KB Output is correct
30 Correct 16 ms 10376 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2480 ms 96244 KB Output is correct
2 Correct 1349 ms 96972 KB Output is correct
3 Correct 2323 ms 95968 KB Output is correct
4 Correct 1294 ms 97124 KB Output is correct
5 Correct 2300 ms 91732 KB Output is correct
6 Correct 1287 ms 96252 KB Output is correct
7 Correct 2301 ms 92844 KB Output is correct
8 Correct 1205 ms 95028 KB Output is correct
9 Correct 2368 ms 85592 KB Output is correct
10 Correct 2265 ms 82756 KB Output is correct
11 Correct 2382 ms 81484 KB Output is correct
12 Correct 2467 ms 84516 KB Output is correct
13 Correct 2347 ms 82240 KB Output is correct
14 Correct 2351 ms 89556 KB Output is correct
15 Correct 2348 ms 84652 KB Output is correct
16 Correct 2368 ms 78480 KB Output is correct
17 Correct 2332 ms 80712 KB Output is correct
18 Correct 2377 ms 84220 KB Output is correct
19 Correct 2406 ms 83184 KB Output is correct
20 Correct 2360 ms 85900 KB Output is correct
21 Correct 8 ms 9676 KB Output is correct

Subtask #4
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 8 ms 9700 KB Output is correct
4 Correct 7 ms 9676 KB Output is correct
5 Correct 7 ms 9704 KB Output is correct
6 Correct 7 ms 9724 KB Output is correct
7 Correct 7 ms 9676 KB Output is correct
8 Correct 7 ms 9640 KB Output is correct
9 Correct 7 ms 9676 KB Output is correct
10 Correct 7 ms 9700 KB Output is correct
11 Correct 14 ms 10188 KB Output is correct
12 Correct 14 ms 10096 KB Output is correct
13 Correct 13 ms 10124 KB Output is correct
14 Correct 15 ms 10088 KB Output is correct
15 Correct 17 ms 10336 KB Output is correct
16 Correct 16 ms 10284 KB Output is correct
17 Correct 12 ms 10224 KB Output is correct
18 Correct 13 ms 10320 KB Output is correct
19 Correct 14 ms 10316 KB Output is correct
20 Correct 14 ms 10188 KB Output is correct
21 Correct 14 ms 10316 KB Output is correct
22 Correct 15 ms 10540 KB Output is correct
23 Correct 17 ms 10436 KB Output is correct
24 Correct 17 ms 10348 KB Output is correct
25 Correct 17 ms 10436 KB Output is correct
26 Correct 18 ms 10404 KB Output is correct
27 Correct 17 ms 10316 KB Output is correct
28 Correct 18 ms 10348 KB Output is correct
29 Correct 17 ms 10416 KB Output is correct
30 Correct 16 ms 10376 KB Output is correct
31 Correct 2480 ms 96244 KB Output is correct
32 Correct 1349 ms 96972 KB Output is correct
33 Correct 2323 ms 95968 KB Output is correct
34 Correct 1294 ms 97124 KB Output is correct
35 Correct 2300 ms 91732 KB Output is correct
36 Correct 1287 ms 96252 KB Output is correct
37 Correct 2301 ms 92844 KB Output is correct
38 Correct 1205 ms 95028 KB Output is correct
39 Correct 2368 ms 85592 KB Output is correct
40 Correct 2265 ms 82756 KB Output is correct
41 Correct 2382 ms 81484 KB Output is correct
42 Correct 2467 ms 84516 KB Output is correct
43 Correct 2347 ms 82240 KB Output is correct
44 Correct 2351 ms 89556 KB Output is correct
45 Correct 2348 ms 84652 KB Output is correct
46 Correct 2368 ms 78480 KB Output is correct
47 Correct 2332 ms 80712 KB Output is correct
48 Correct 2377 ms 84220 KB Output is correct
49 Correct 2406 ms 83184 KB Output is correct
50 Correct 2360 ms 85900 KB Output is correct
51 Correct 8 ms 9676 KB Output is correct
52 Correct 1758 ms 57768 KB Output is correct
53 Correct 1864 ms 60368 KB Output is correct
54 Correct 1847 ms 58964 KB Output is correct
55 Correct 1900 ms 59380 KB Output is correct
56 Correct 1851 ms 61188 KB Output is correct
57 Correct 1855 ms 58964 KB Output is correct
58 Correct 2369 ms 69592 KB Output is correct
59 Correct 2157 ms 61660 KB Output is correct
60 Correct 2343 ms 69060 KB Output is correct
61 Correct 2594 ms 67280 KB Output is correct
62 Correct 1372 ms 96956 KB Output is correct
63 Correct 1341 ms 97052 KB Output is correct
64 Correct 1268 ms 94140 KB Output is correct
65 Correct 1322 ms 96920 KB Output is correct
66 Correct 1244 ms 71060 KB Output is correct
67 Correct 1301 ms 69960 KB Output is correct
68 Correct 1345 ms 70968 KB Output is correct
69 Correct 1333 ms 68212 KB Output is correct
70 Correct 1313 ms 68220 KB Output is correct
71 Correct 1279 ms 69772 KB Output is correct
72 Correct 1279 ms 69688 KB Output is correct
73 Correct 1312 ms 66532 KB Output is correct
74 Correct 1363 ms 69792 KB Output is correct
75 Correct 1341 ms 68004 KB Output is correct
76 Correct 2840 ms 81320 KB Output is correct
77 Correct 2808 ms 77920 KB Output is correct
78 Correct 2490 ms 79160 KB Output is correct
79 Correct 2347 ms 76676 KB Output is correct
80 Correct 2343 ms 90120 KB Output is correct
81 Correct 2444 ms 85852 KB Output is correct
82 Correct 2405 ms 86012 KB Output is correct
83 Correct 2347 ms 81844 KB Output is correct
84 Correct 2435 ms 88948 KB Output is correct
85 Correct 2386 ms 87172 KB Output is correct
86 Correct 2444 ms 76684 KB Output is correct
87 Correct 2430 ms 79172 KB Output is correct
88 Correct 2352 ms 80044 KB Output is correct
89 Correct 2246 ms 75124 KB Output is correct
90 Correct 2314 ms 74996 KB Output is correct
91 Correct 2277 ms 77612 KB Output is correct
92 Correct 2242 ms 72352 KB Output is correct
93 Correct 2246 ms 71880 KB Output is correct
94 Correct 2217 ms 71280 KB Output is correct
95 Correct 2389 ms 76984 KB Output is correct
96 Correct 2260 ms 75112 KB Output is correct
97 Correct 2288 ms 73968 KB Output is correct