oj.uz

Submission #706229

# Submission time Handle Problem Language Result Execution time Memory
706229 2023-03-06T06:56:31 Z alvingogo Mergers (JOI19_mergers) C++14
100 / 100
 2763 ms 161792 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

/* Merger:
first, find out the LCA of all stages

second, for each node find out whether we can cut the edge its father to the node, which can be done by storing every node's stage's LCA
if all its subtree's node's stage's LCA is in its subtree then we can cut it

last, for all the node we can build a virtual tree
we know that if we see the edges between virtual tree's node to node as a stage, the answer won't change

if we merge two stages, then the nodes on the path of the two stages are all uncuttable, so we only have to find out the minimum path cover

and i think it's equal to (the number of leaf (deg == 1) + 1) / 2, done!

guess a few coding will lead us to the ac :happy_mention:
*/
vector<int> e;
struct no{
	vector<int> ch,ch2;
	int as[21]={0};
	int dep=-1;
	int md=1e9;
	int in=0;
	int t;
};
vector<no> v;
vector<int> can;
int cnt=0;
void dfs(int r,int f){
	v[r].dep=v[f].dep+1;
	v[r].as[0]=f;
	v[r].in=cnt;
	cnt++;
	for(auto h:v[r].ch){
		if(h!=f){
			dfs(h,r);
		}
	}
}
void dfs2(int r,int f){
	v[r].md=v[e[v[r].t]].dep;
	for(auto h:v[r].ch){
		if(h!=f){
			dfs2(h,r);
			v[r].md=min(v[r].md,v[h].md);
		}
	}
	if(r!=f){
		if(v[r].md>=v[r].dep){
			can.push_back(f);
			can.push_back(r);
		}
	}
}
int lca(int a,int b){
	if(v[a].dep<v[b].dep){
		swap(a,b);
	}
	for(int i=20;i>=0;i--){
		if(v[v[a].as[i]].dep>=v[b].dep){
			a=v[a].as[i];
		}
	}
	if(a==b){
		return a;
	}
	for(int i=20;i>=0;i--){
		if(v[a].as[i]!=v[b].as[i]){
			a=v[a].as[i];
			b=v[b].as[i];
		}
	}
	return v[a].as[0];
}
bool cmp(int a,int b){
	return v[a].in<v[b].in;
}
int bvt(vector<int> x,int flag){
	sort(x.begin(),x.end(),cmp);
	int u=x.size();
	for(int i=1;i<u;i++){
		x.push_back(lca(x[i],x[i-1]));
	}
	sort(x.begin(),x.end(),cmp);
	if(flag==1){	
		x.erase(unique(x.begin(),x.end()),x.end());
		u=x.size();
		for(int i=0;i<u-1;i++){
			int z=lca(x[i],x[i+1]);
			v[z].ch2.push_back(x[i+1]);
			v[x[i+1]].ch2.push_back(z);
		}
		can=x;
	}
	return x[0];
}
int main(){
	AquA;
	int n,k;
	cin >> n >> k;
	v.resize(n);
	e.resize(k);
	for(int i=1;i<n;i++){
		int a,b;
		cin >> a >> b;
		a--;
		b--;
		v[a].ch.push_back(b);
		v[b].ch.push_back(a);
	}
	dfs(0,0);
	for(int i=1;i<21;i++){
		for(int j=0;j<n;j++){
			v[j].as[i]=v[v[j].as[i-1]].as[i-1];
		}
	}
	vector<vector<int> > gg(k);
	for(int i=0;i<n;i++){
		int a;
		cin >> a;
		a--;
		v[i].t=a;
		gg[a].push_back(i);
	}
	for(int i=0;i<k;i++){
		e[i]=bvt(gg[i],0);
	}
	dfs2(0,0);
	if(!can.size()){
		cout << 0 << "\n";
		return 0;
	}
	if(can.size()==1){
		cout << 1 << "\n";
		return 0;
	}
	sort(can.begin(),can.end());
	can.erase(unique(can.begin(),can.end()),can.end());
	bvt(can,1);
	int ans=0;
	for(auto h:can){
		if(v[h].ch2.size()==1){
			ans++;
		}
	}
	cout << (ans+1)/2 << '\n';
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 316 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 312 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 320 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 316 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 316 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 312 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 320 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 316 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 4 ms 1108 KB Output is correct
27 Correct 3 ms 852 KB Output is correct
28 Correct 5 ms 1236 KB Output is correct
29 Correct 5 ms 1236 KB Output is correct
30 Correct 3 ms 852 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 3 ms 1108 KB Output is correct
33 Correct 0 ms 340 KB Output is correct
34 Correct 3 ms 844 KB Output is correct
35 Correct 5 ms 1188 KB Output is correct
36 Correct 4 ms 936 KB Output is correct
37 Correct 3 ms 980 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Correct 3 ms 980 KB Output is correct
40 Correct 3 ms 852 KB Output is correct
41 Correct 3 ms 852 KB Output is correct
42 Correct 3 ms 980 KB Output is correct
43 Correct 3 ms 968 KB Output is correct
44 Correct 1 ms 340 KB Output is correct
45 Correct 3 ms 1012 KB Output is correct
46 Correct 3 ms 980 KB Output is correct
47 Correct 1 ms 324 KB Output is correct
48 Correct 4 ms 888 KB Output is correct
49 Correct 4 ms 1256 KB Output is correct
50 Correct 6 ms 1236 KB Output is correct
51 Correct 4 ms 972 KB Output is correct
52 Correct 3 ms 856 KB Output is correct
53 Correct 4 ms 980 KB Output is correct
54 Correct 4 ms 844 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 316 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 312 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 320 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 316 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 124 ms 20112 KB Output is correct
27 Correct 190 ms 19776 KB Output is correct
28 Correct 3 ms 852 KB Output is correct
29 Correct 0 ms 316 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 167 ms 19620 KB Output is correct
32 Correct 3 ms 852 KB Output is correct
33 Correct 280 ms 23984 KB Output is correct
34 Correct 188 ms 19692 KB Output is correct
35 Correct 4 ms 852 KB Output is correct
36 Correct 191 ms 20080 KB Output is correct
37 Correct 3 ms 844 KB Output is correct
38 Correct 3 ms 856 KB Output is correct
39 Correct 122 ms 20036 KB Output is correct
40 Correct 5 ms 968 KB Output is correct
41 Correct 216 ms 20520 KB Output is correct
42 Correct 262 ms 21144 KB Output is correct
43 Correct 1 ms 340 KB Output is correct
44 Correct 293 ms 24104 KB Output is correct
45 Correct 256 ms 21860 KB Output is correct
46 Correct 4 ms 844 KB Output is correct
47 Correct 3 ms 852 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 19916 KB Output is correct
2 Correct 230 ms 30348 KB Output is correct
3 Correct 5 ms 1132 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 3 ms 852 KB Output is correct
8 Correct 190 ms 23040 KB Output is correct
9 Correct 3 ms 852 KB Output is correct
10 Correct 152 ms 19820 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 163 ms 19772 KB Output is correct
13 Correct 251 ms 23568 KB Output is correct
14 Correct 375 ms 29864 KB Output is correct
15 Correct 119 ms 20036 KB Output is correct
16 Correct 3 ms 980 KB Output is correct
17 Correct 1 ms 320 KB Output is correct
18 Correct 212 ms 28860 KB Output is correct
19 Correct 378 ms 32152 KB Output is correct
20 Correct 3 ms 980 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 129 ms 23360 KB Output is correct
23 Correct 4 ms 972 KB Output is correct
24 Correct 183 ms 20964 KB Output is correct
25 Correct 319 ms 31160 KB Output is correct
26 Correct 5 ms 1236 KB Output is correct
27 Correct 7 ms 1212 KB Output is correct
28 Correct 3 ms 980 KB Output is correct
29 Correct 3 ms 852 KB Output is correct
30 Correct 3 ms 980 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 316 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 312 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 320 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 316 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 4 ms 1108 KB Output is correct
27 Correct 3 ms 852 KB Output is correct
28 Correct 5 ms 1236 KB Output is correct
29 Correct 5 ms 1236 KB Output is correct
30 Correct 3 ms 852 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 3 ms 1108 KB Output is correct
33 Correct 0 ms 340 KB Output is correct
34 Correct 3 ms 844 KB Output is correct
35 Correct 5 ms 1188 KB Output is correct
36 Correct 4 ms 936 KB Output is correct
37 Correct 3 ms 980 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Correct 3 ms 980 KB Output is correct
40 Correct 3 ms 852 KB Output is correct
41 Correct 3 ms 852 KB Output is correct
42 Correct 3 ms 980 KB Output is correct
43 Correct 3 ms 968 KB Output is correct
44 Correct 1 ms 340 KB Output is correct
45 Correct 3 ms 1012 KB Output is correct
46 Correct 3 ms 980 KB Output is correct
47 Correct 1 ms 324 KB Output is correct
48 Correct 4 ms 888 KB Output is correct
49 Correct 4 ms 1256 KB Output is correct
50 Correct 6 ms 1236 KB Output is correct
51 Correct 4 ms 972 KB Output is correct
52 Correct 3 ms 856 KB Output is correct
53 Correct 4 ms 980 KB Output is correct
54 Correct 4 ms 844 KB Output is correct
55 Correct 1 ms 212 KB Output is correct
56 Correct 124 ms 20112 KB Output is correct
57 Correct 190 ms 19776 KB Output is correct
58 Correct 3 ms 852 KB Output is correct
59 Correct 0 ms 316 KB Output is correct
60 Correct 1 ms 212 KB Output is correct
61 Correct 167 ms 19620 KB Output is correct
62 Correct 3 ms 852 KB Output is correct
63 Correct 280 ms 23984 KB Output is correct
64 Correct 188 ms 19692 KB Output is correct
65 Correct 4 ms 852 KB Output is correct
66 Correct 191 ms 20080 KB Output is correct
67 Correct 3 ms 844 KB Output is correct
68 Correct 3 ms 856 KB Output is correct
69 Correct 122 ms 20036 KB Output is correct
70 Correct 5 ms 968 KB Output is correct
71 Correct 216 ms 20520 KB Output is correct
72 Correct 262 ms 21144 KB Output is correct
73 Correct 1 ms 340 KB Output is correct
74 Correct 293 ms 24104 KB Output is correct
75 Correct 256 ms 21860 KB Output is correct
76 Correct 4 ms 844 KB Output is correct
77 Correct 3 ms 852 KB Output is correct
78 Correct 131 ms 19916 KB Output is correct
79 Correct 230 ms 30348 KB Output is correct
80 Correct 5 ms 1132 KB Output is correct
81 Correct 3 ms 852 KB Output is correct
82 Correct 1 ms 212 KB Output is correct
83 Correct 1 ms 212 KB Output is correct
84 Correct 3 ms 852 KB Output is correct
85 Correct 190 ms 23040 KB Output is correct
86 Correct 3 ms 852 KB Output is correct
87 Correct 152 ms 19820 KB Output is correct
88 Correct 1 ms 340 KB Output is correct
89 Correct 163 ms 19772 KB Output is correct
90 Correct 251 ms 23568 KB Output is correct
91 Correct 375 ms 29864 KB Output is correct
92 Correct 119 ms 20036 KB Output is correct
93 Correct 3 ms 980 KB Output is correct
94 Correct 1 ms 320 KB Output is correct
95 Correct 212 ms 28860 KB Output is correct
96 Correct 378 ms 32152 KB Output is correct
97 Correct 3 ms 980 KB Output is correct
98 Correct 1 ms 340 KB Output is correct
99 Correct 129 ms 23360 KB Output is correct
100 Correct 4 ms 972 KB Output is correct
101 Correct 183 ms 20964 KB Output is correct
102 Correct 319 ms 31160 KB Output is correct
103 Correct 5 ms 1236 KB Output is correct
104 Correct 7 ms 1212 KB Output is correct
105 Correct 3 ms 980 KB Output is correct
106 Correct 3 ms 852 KB Output is correct
107 Correct 3 ms 980 KB Output is correct
108 Correct 764 ms 107288 KB Output is correct
109 Correct 2247 ms 107348 KB Output is correct
110 Correct 2075 ms 111268 KB Output is correct
111 Correct 2763 ms 156324 KB Output is correct
112 Correct 2347 ms 159608 KB Output is correct
113 Correct 1522 ms 149212 KB Output is correct
114 Correct 1712 ms 103284 KB Output is correct
115 Correct 1844 ms 104608 KB Output is correct
116 Correct 1036 ms 108052 KB Output is correct
117 Correct 2245 ms 154196 KB Output is correct
118 Correct 921 ms 100604 KB Output is correct
119 Correct 2127 ms 154216 KB Output is correct
120 Correct 2405 ms 161792 KB Output is correct
121 Correct 2143 ms 154168 KB Output is correct
122 Correct 1361 ms 125796 KB Output is correct
123 Correct 1481 ms 157132 KB Output is correct
124 Correct 1958 ms 142244 KB Output is correct