oj.uz

Submission #623483

# Submission time Handle Problem Language Result Execution time Memory
623483 2022-08-05T16:46:08 Z errorgorn Capital City (JOI20_capital_city) C++17
100 / 100
 1653 ms 50168 KB 
//もう布団の中から出たくない
//布団の外は寒すぎるから
//布団の中から出たくない
//布団の中はあたたかすぎるから

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

#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n,k;
vector<int> al[200005];
int arr[200005];
vector<int> pos[200005];

int ans=1e9;
int ss[200005];
bool used[200005];

void dfs_ss(int i,int p){
	ss[i]=1;
	for (auto it:al[i]){
		if (it==p || used[it]) continue;
		dfs_ss(it,i);
		ss[i]+=ss[it];
	}
}

int pp[200005];
set<int> s;
void dfs(int i,int p){
	s.insert(i);
	pp[i]=p;
	for (auto it:al[i]){
		if (it==p || used[it]) continue;
		dfs(it,i);
	}
}

bool vis[200005];
bool vis2[200005];

void centroid(int i){
	dfs_ss(i,-1);
	
	int curr=i,currp=-1;
	while (true){
		bool done=true;
		for (auto it:al[curr]){
			if (it==currp || used[it]) continue;
			
			if (ss[it]>=(ss[i]+1)/2){
				currp=curr;
				curr=it;
				done=false;
				break;
			}
		}
		if (done) break;
	}
	
	s.clear();
	dfs(curr,-1);
	
	for (auto it:s) vis[it]=vis2[arr[it]]=false;
	vis[curr]=true;
	vector<int> stk={curr};
	int val=0;
	while (!stk.empty()){
		int u=stk.back(); stk.pob();
		
		if (!vis2[arr[u]]){
			vis2[arr[u]]=true;
			val++;
			
			for (auto it:pos[arr[u]]){
				if (!s.count(it)) goto skip;
				if (!vis[it]){
					vis[it]=true;
					stk.pub(it);
				}
			}
		}
		if (pp[u]!=-1 && !vis[pp[u]]){
			vis[pp[u]]=true;
			stk.pub(pp[u]);
		}
	}
	
	ans=min(ans,val);
	
	skip:;
	
	used[curr]=true;
	for (auto it:al[curr]) if (!used[it]) centroid(it);
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n>>k;
	
	int a,b;
	rep(x,1,n){
		cin>>a>>b;
		al[a].pub(b);
		al[b].pub(a);
	}
	rep(x,1,n+1) cin>>arr[x];
	rep(x,1,n+1) pos[arr[x]].pub(x);
	
	centroid(1);
	
	cout<<ans-1<<endl;
}

Subtask #1
1.0 / 1.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 7 ms 9684 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 8 ms 9940 KB Output is correct
12 Correct 11 ms 9956 KB Output is correct
13 Correct 9 ms 9940 KB Output is correct
14 Correct 7 ms 9964 KB Output is correct
15 Correct 8 ms 10044 KB Output is correct
16 Correct 8 ms 9984 KB Output is correct
17 Correct 7 ms 10068 KB Output is correct
18 Correct 7 ms 10068 KB Output is correct
19 Correct 7 ms 10068 KB Output is correct
20 Correct 8 ms 9940 KB Output is correct
21 Correct 7 ms 10068 KB Output is correct
22 Correct 7 ms 10104 KB Output is correct
23 Correct 8 ms 9940 KB Output is correct
24 Correct 12 ms 10036 KB Output is correct
25 Correct 10 ms 10068 KB Output is correct
26 Correct 9 ms 10068 KB Output is correct
27 Correct 11 ms 10068 KB Output is correct
28 Correct 10 ms 10068 KB Output is correct
29 Correct 9 ms 10060 KB Output is correct
30 Correct 12 ms 9960 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1421 ms 45796 KB Output is correct
2 Correct 479 ms 46380 KB Output is correct
3 Correct 1392 ms 45620 KB Output is correct
4 Correct 485 ms 46180 KB Output is correct
5 Correct 1386 ms 43476 KB Output is correct
6 Correct 492 ms 49852 KB Output is correct
7 Correct 1284 ms 47476 KB Output is correct
8 Correct 525 ms 50048 KB Output is correct
9 Correct 1551 ms 46804 KB Output is correct
10 Correct 1590 ms 44832 KB Output is correct
11 Correct 1555 ms 47332 KB Output is correct
12 Correct 1482 ms 49432 KB Output is correct
13 Correct 1602 ms 44524 KB Output is correct
14 Correct 1508 ms 49488 KB Output is correct
15 Correct 1601 ms 49496 KB Output is correct
16 Correct 1487 ms 45468 KB Output is correct
17 Correct 1567 ms 45824 KB Output is correct
18 Correct 1590 ms 45996 KB Output is correct
19 Correct 1580 ms 48660 KB Output is correct
20 Correct 1491 ms 50168 KB Output is correct
21 Correct 5 ms 9684 KB Output is correct

Subtask #4
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 7 ms 9684 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 8 ms 9940 KB Output is correct
12 Correct 11 ms 9956 KB Output is correct
13 Correct 9 ms 9940 KB Output is correct
14 Correct 7 ms 9964 KB Output is correct
15 Correct 8 ms 10044 KB Output is correct
16 Correct 8 ms 9984 KB Output is correct
17 Correct 7 ms 10068 KB Output is correct
18 Correct 7 ms 10068 KB Output is correct
19 Correct 7 ms 10068 KB Output is correct
20 Correct 8 ms 9940 KB Output is correct
21 Correct 7 ms 10068 KB Output is correct
22 Correct 7 ms 10104 KB Output is correct
23 Correct 8 ms 9940 KB Output is correct
24 Correct 12 ms 10036 KB Output is correct
25 Correct 10 ms 10068 KB Output is correct
26 Correct 9 ms 10068 KB Output is correct
27 Correct 11 ms 10068 KB Output is correct
28 Correct 10 ms 10068 KB Output is correct
29 Correct 9 ms 10060 KB Output is correct
30 Correct 12 ms 9960 KB Output is correct
31 Correct 1421 ms 45796 KB Output is correct
32 Correct 479 ms 46380 KB Output is correct
33 Correct 1392 ms 45620 KB Output is correct
34 Correct 485 ms 46180 KB Output is correct
35 Correct 1386 ms 43476 KB Output is correct
36 Correct 492 ms 49852 KB Output is correct
37 Correct 1284 ms 47476 KB Output is correct
38 Correct 525 ms 50048 KB Output is correct
39 Correct 1551 ms 46804 KB Output is correct
40 Correct 1590 ms 44832 KB Output is correct
41 Correct 1555 ms 47332 KB Output is correct
42 Correct 1482 ms 49432 KB Output is correct
43 Correct 1602 ms 44524 KB Output is correct
44 Correct 1508 ms 49488 KB Output is correct
45 Correct 1601 ms 49496 KB Output is correct
46 Correct 1487 ms 45468 KB Output is correct
47 Correct 1567 ms 45824 KB Output is correct
48 Correct 1590 ms 45996 KB Output is correct
49 Correct 1580 ms 48660 KB Output is correct
50 Correct 1491 ms 50168 KB Output is correct
51 Correct 5 ms 9684 KB Output is correct
52 Correct 966 ms 39636 KB Output is correct
53 Correct 1077 ms 39612 KB Output is correct
54 Correct 1047 ms 39660 KB Output is correct
55 Correct 1151 ms 39668 KB Output is correct
56 Correct 1170 ms 39588 KB Output is correct
57 Correct 1087 ms 39680 KB Output is correct
58 Correct 1283 ms 40900 KB Output is correct
59 Correct 1324 ms 41640 KB Output is correct
60 Correct 1653 ms 40668 KB Output is correct
61 Correct 1375 ms 40220 KB Output is correct
62 Correct 502 ms 49860 KB Output is correct
63 Correct 475 ms 49964 KB Output is correct
64 Correct 504 ms 49864 KB Output is correct
65 Correct 494 ms 49936 KB Output is correct
66 Correct 932 ms 44908 KB Output is correct
67 Correct 877 ms 44864 KB Output is correct
68 Correct 822 ms 44904 KB Output is correct
69 Correct 885 ms 44920 KB Output is correct
70 Correct 796 ms 44864 KB Output is correct
71 Correct 827 ms 44924 KB Output is correct
72 Correct 859 ms 44832 KB Output is correct
73 Correct 918 ms 44224 KB Output is correct
74 Correct 833 ms 44956 KB Output is correct
75 Correct 907 ms 44944 KB Output is correct
76 Correct 1420 ms 43424 KB Output is correct
77 Correct 1489 ms 42072 KB Output is correct
78 Correct 1522 ms 45680 KB Output is correct
79 Correct 1561 ms 44200 KB Output is correct
80 Correct 1493 ms 49688 KB Output is correct
81 Correct 1519 ms 46964 KB Output is correct
82 Correct 1390 ms 47064 KB Output is correct
83 Correct 1476 ms 44432 KB Output is correct
84 Correct 1529 ms 49088 KB Output is correct
85 Correct 1507 ms 48028 KB Output is correct
86 Correct 1502 ms 44004 KB Output is correct
87 Correct 1535 ms 45472 KB Output is correct
88 Correct 1431 ms 47072 KB Output is correct
89 Correct 1392 ms 43716 KB Output is correct
90 Correct 1387 ms 43532 KB Output is correct
91 Correct 1251 ms 45412 KB Output is correct
92 Correct 1385 ms 44680 KB Output is correct
93 Correct 1369 ms 44276 KB Output is correct
94 Correct 1442 ms 43680 KB Output is correct
95 Correct 1393 ms 45060 KB Output is correct
96 Correct 1229 ms 43888 KB Output is correct
97 Correct 1417 ms 45636 KB Output is correct