답안 #128273

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
128273	2019-07-10T15:48:10 Z	mohammedehab2002	Mergers (JOI19_mergers)	C++11	100 / 100	1603 ms	144248 KB

mergers

#include <iostream>
#include <vector>
#include <set>
using namespace std;
int st[500005],dep[500005],dp[20][500005],q[500005],par[500005],deg[500005];
set<pair<int,int> > s;
vector<int> v[500005],inv[500005],comp[500005];
void pre(int node,int p)
{
	dep[node]=dep[p]+1;
	dp[0][node]=p;
	for (int i=1;i<20;i++)
	dp[i][node]=dp[i-1][dp[i-1][node]];
	for (int u:v[node])
	{
		if (u!=p)
		pre(u,node);
	}
}
int lca(int u,int v)
{
	if (dep[u]<dep[v])
	swap(u,v);
	int dist=dep[u]-dep[v];
	for (int i=0;i<20;i++)
	{
		if (dist&(1<<i))
		u=dp[i][u];
	}
	if (u==v)
	return u;
	for (int i=19;i>=0;i--)
	{
		if (dp[i][u]!=dp[i][v])
		{
			u=dp[i][u];
			v=dp[i][v];
		}
	}
	return dp[0][u];
}
int find(int x)
{
	if (par[x]!=x)
	par[x]=find(par[x]);
	return par[x];
}
void Union(int x,int y)
{
	x=find(x);
	y=find(y);
	if (x!=y)
	par[x]=y;
}
void update(int u,int v)
{
	while (dep[u]>dep[v])
	{
		Union(u,dp[0][u]);
		u=find(u);
	}
}
void get(int node,int p,int to)
{
	for (int u:v[node])
	{
		if (u!=p)
		{
			if (find(u)==find(node))
			get(u,node,to);
			else
			{
				deg[to]++;
				deg[u]++;
				get(u,node,u);
			}
		}
	}
}
int main()
{
	int n,k;
	scanf("%d%d",&n,&k);
	for (int i=1;i<n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for (int i=1;i<=n;i++)
	{
		par[i]=i;
		scanf("%d",&st[i]);
		inv[st[i]].push_back(i);
	}
	pre(1,0);
	for (int i=1;i<=k;i++)
	{
		int node=inv[i][0];
		for (int u:inv[i])
		node=lca(node,u);
		for (int u:inv[i])
		q[u]=node;
	}
	for (int i=1;i<=n;i++)
	update(i,q[i]);
	get(1,0,1);
	int cnt=0;
	for (int i=1;i<=n;i++)
	cnt+=(deg[i]==1);
	printf("%d",(cnt+1)/2);
}

Compilation message

mergers.cpp: In function 'int main()':
mergers.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&k);
  ~~~~~^~~~~~~~~~~~~~
mergers.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a,&b);
   ~~~~~^~~~~~~~~~~~~~
mergers.cpp:94:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&st[i]);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	36 ms	35704 KB	Output is correct
2	Correct	42 ms	35704 KB	Output is correct
3	Correct	35 ms	35704 KB	Output is correct
4	Correct	36 ms	35704 KB	Output is correct
5	Correct	36 ms	35832 KB	Output is correct
6	Correct	36 ms	35704 KB	Output is correct
7	Correct	35 ms	35704 KB	Output is correct
8	Correct	36 ms	35704 KB	Output is correct
9	Correct	35 ms	35704 KB	Output is correct
10	Correct	42 ms	35704 KB	Output is correct
11	Correct	36 ms	35704 KB	Output is correct
12	Correct	36 ms	35704 KB	Output is correct
13	Correct	41 ms	35832 KB	Output is correct
14	Correct	42 ms	35704 KB	Output is correct
15	Correct	45 ms	35808 KB	Output is correct
16	Correct	42 ms	35704 KB	Output is correct
17	Correct	37 ms	35704 KB	Output is correct
18	Correct	36 ms	35832 KB	Output is correct
19	Correct	41 ms	35684 KB	Output is correct
20	Correct	38 ms	35704 KB	Output is correct
21	Correct	48 ms	35704 KB	Output is correct
22	Correct	60 ms	35788 KB	Output is correct
23	Correct	35 ms	35704 KB	Output is correct
24	Correct	35 ms	35704 KB	Output is correct

Subtask #2
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	36 ms	35704 KB	Output is correct
2	Correct	42 ms	35704 KB	Output is correct
3	Correct	35 ms	35704 KB	Output is correct
4	Correct	36 ms	35704 KB	Output is correct
5	Correct	36 ms	35832 KB	Output is correct
6	Correct	36 ms	35704 KB	Output is correct
7	Correct	35 ms	35704 KB	Output is correct
8	Correct	36 ms	35704 KB	Output is correct
9	Correct	35 ms	35704 KB	Output is correct
10	Correct	42 ms	35704 KB	Output is correct
11	Correct	36 ms	35704 KB	Output is correct
12	Correct	36 ms	35704 KB	Output is correct
13	Correct	41 ms	35832 KB	Output is correct
14	Correct	42 ms	35704 KB	Output is correct
15	Correct	45 ms	35808 KB	Output is correct
16	Correct	42 ms	35704 KB	Output is correct
17	Correct	37 ms	35704 KB	Output is correct
18	Correct	36 ms	35832 KB	Output is correct
19	Correct	41 ms	35684 KB	Output is correct
20	Correct	38 ms	35704 KB	Output is correct
21	Correct	48 ms	35704 KB	Output is correct
22	Correct	60 ms	35788 KB	Output is correct
23	Correct	35 ms	35704 KB	Output is correct
24	Correct	35 ms	35704 KB	Output is correct
25	Correct	40 ms	35704 KB	Output is correct
26	Correct	48 ms	36196 KB	Output is correct
27	Correct	47 ms	36216 KB	Output is correct
28	Correct	47 ms	36344 KB	Output is correct
29	Correct	38 ms	36216 KB	Output is correct
30	Correct	38 ms	36216 KB	Output is correct
31	Correct	59 ms	35704 KB	Output is correct
32	Correct	39 ms	36472 KB	Output is correct
33	Correct	36 ms	35832 KB	Output is correct
34	Correct	37 ms	36216 KB	Output is correct
35	Correct	39 ms	36188 KB	Output is correct
36	Correct	38 ms	36088 KB	Output is correct
37	Correct	38 ms	36188 KB	Output is correct
38	Correct	35 ms	35704 KB	Output is correct
39	Correct	46 ms	36212 KB	Output is correct
40	Correct	45 ms	36088 KB	Output is correct
41	Correct	38 ms	36216 KB	Output is correct
42	Correct	38 ms	36216 KB	Output is correct
43	Correct	39 ms	36468 KB	Output is correct
44	Correct	36 ms	35704 KB	Output is correct
45	Correct	40 ms	36472 KB	Output is correct
46	Correct	46 ms	36252 KB	Output is correct
47	Correct	36 ms	35808 KB	Output is correct
48	Correct	39 ms	36216 KB	Output is correct
49	Correct	43 ms	36320 KB	Output is correct
50	Correct	39 ms	36344 KB	Output is correct
51	Correct	47 ms	36216 KB	Output is correct
52	Correct	39 ms	36216 KB	Output is correct
53	Correct	45 ms	36216 KB	Output is correct
54	Correct	38 ms	36216 KB	Output is correct

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	36 ms	35704 KB	Output is correct
2	Correct	42 ms	35704 KB	Output is correct
3	Correct	35 ms	35704 KB	Output is correct
4	Correct	36 ms	35704 KB	Output is correct
5	Correct	36 ms	35832 KB	Output is correct
6	Correct	36 ms	35704 KB	Output is correct
7	Correct	35 ms	35704 KB	Output is correct
8	Correct	36 ms	35704 KB	Output is correct
9	Correct	35 ms	35704 KB	Output is correct
10	Correct	42 ms	35704 KB	Output is correct
11	Correct	36 ms	35704 KB	Output is correct
12	Correct	36 ms	35704 KB	Output is correct
13	Correct	41 ms	35832 KB	Output is correct
14	Correct	42 ms	35704 KB	Output is correct
15	Correct	45 ms	35808 KB	Output is correct
16	Correct	42 ms	35704 KB	Output is correct
17	Correct	37 ms	35704 KB	Output is correct
18	Correct	36 ms	35832 KB	Output is correct
19	Correct	41 ms	35684 KB	Output is correct
20	Correct	38 ms	35704 KB	Output is correct
21	Correct	48 ms	35704 KB	Output is correct
22	Correct	60 ms	35788 KB	Output is correct
23	Correct	35 ms	35704 KB	Output is correct
24	Correct	35 ms	35704 KB	Output is correct
25	Correct	42 ms	35704 KB	Output is correct
26	Correct	149 ms	49492 KB	Output is correct
27	Correct	197 ms	49144 KB	Output is correct
28	Correct	38 ms	36264 KB	Output is correct
29	Correct	36 ms	35704 KB	Output is correct
30	Correct	39 ms	35704 KB	Output is correct
31	Correct	234 ms	49124 KB	Output is correct
32	Correct	48 ms	36216 KB	Output is correct
33	Correct	243 ms	56272 KB	Output is correct
34	Correct	250 ms	50296 KB	Output is correct
35	Correct	46 ms	36136 KB	Output is correct
36	Correct	273 ms	51124 KB	Output is correct
37	Correct	38 ms	36216 KB	Output is correct
38	Correct	47 ms	36220 KB	Output is correct
39	Correct	184 ms	50540 KB	Output is correct
40	Correct	61 ms	36472 KB	Output is correct
41	Correct	219 ms	50204 KB	Output is correct
42	Correct	294 ms	52600 KB	Output is correct
43	Correct	37 ms	35704 KB	Output is correct
44	Correct	243 ms	57740 KB	Output is correct
45	Correct	233 ms	54136 KB	Output is correct
46	Correct	46 ms	36212 KB	Output is correct
47	Correct	39 ms	36088 KB	Output is correct

Subtask #4
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	149 ms	49136 KB	Output is correct
2	Correct	185 ms	52348 KB	Output is correct
3	Correct	47 ms	36216 KB	Output is correct
4	Correct	48 ms	36216 KB	Output is correct
5	Correct	36 ms	35704 KB	Output is correct
6	Correct	36 ms	35780 KB	Output is correct
7	Correct	38 ms	36216 KB	Output is correct
8	Correct	240 ms	50436 KB	Output is correct
9	Correct	38 ms	36088 KB	Output is correct
10	Correct	245 ms	49276 KB	Output is correct
11	Correct	36 ms	35704 KB	Output is correct
12	Correct	218 ms	49272 KB	Output is correct
13	Correct	228 ms	50296 KB	Output is correct
14	Correct	218 ms	51908 KB	Output is correct
15	Correct	161 ms	49300 KB	Output is correct
16	Correct	46 ms	36216 KB	Output is correct
17	Correct	41 ms	35704 KB	Output is correct
18	Correct	194 ms	51880 KB	Output is correct
19	Correct	249 ms	55800 KB	Output is correct
20	Correct	39 ms	36216 KB	Output is correct
21	Correct	32 ms	35700 KB	Output is correct
22	Correct	187 ms	50668 KB	Output is correct
23	Correct	38 ms	36216 KB	Output is correct
24	Correct	224 ms	49592 KB	Output is correct
25	Correct	243 ms	54448 KB	Output is correct
26	Correct	38 ms	36216 KB	Output is correct
27	Correct	38 ms	36216 KB	Output is correct
28	Correct	39 ms	36216 KB	Output is correct
29	Correct	37 ms	36216 KB	Output is correct
30	Correct	38 ms	36216 KB	Output is correct

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	36 ms	35704 KB	Output is correct
2	Correct	42 ms	35704 KB	Output is correct
3	Correct	35 ms	35704 KB	Output is correct
4	Correct	36 ms	35704 KB	Output is correct
5	Correct	36 ms	35832 KB	Output is correct
6	Correct	36 ms	35704 KB	Output is correct
7	Correct	35 ms	35704 KB	Output is correct
8	Correct	36 ms	35704 KB	Output is correct
9	Correct	35 ms	35704 KB	Output is correct
10	Correct	42 ms	35704 KB	Output is correct
11	Correct	36 ms	35704 KB	Output is correct
12	Correct	36 ms	35704 KB	Output is correct
13	Correct	41 ms	35832 KB	Output is correct
14	Correct	42 ms	35704 KB	Output is correct
15	Correct	45 ms	35808 KB	Output is correct
16	Correct	42 ms	35704 KB	Output is correct
17	Correct	37 ms	35704 KB	Output is correct
18	Correct	36 ms	35832 KB	Output is correct
19	Correct	41 ms	35684 KB	Output is correct
20	Correct	38 ms	35704 KB	Output is correct
21	Correct	48 ms	35704 KB	Output is correct
22	Correct	60 ms	35788 KB	Output is correct
23	Correct	35 ms	35704 KB	Output is correct
24	Correct	35 ms	35704 KB	Output is correct
25	Correct	40 ms	35704 KB	Output is correct
26	Correct	48 ms	36196 KB	Output is correct
27	Correct	47 ms	36216 KB	Output is correct
28	Correct	47 ms	36344 KB	Output is correct
29	Correct	38 ms	36216 KB	Output is correct
30	Correct	38 ms	36216 KB	Output is correct
31	Correct	59 ms	35704 KB	Output is correct
32	Correct	39 ms	36472 KB	Output is correct
33	Correct	36 ms	35832 KB	Output is correct
34	Correct	37 ms	36216 KB	Output is correct
35	Correct	39 ms	36188 KB	Output is correct
36	Correct	38 ms	36088 KB	Output is correct
37	Correct	38 ms	36188 KB	Output is correct
38	Correct	35 ms	35704 KB	Output is correct
39	Correct	46 ms	36212 KB	Output is correct
40	Correct	45 ms	36088 KB	Output is correct
41	Correct	38 ms	36216 KB	Output is correct
42	Correct	38 ms	36216 KB	Output is correct
43	Correct	39 ms	36468 KB	Output is correct
44	Correct	36 ms	35704 KB	Output is correct
45	Correct	40 ms	36472 KB	Output is correct
46	Correct	46 ms	36252 KB	Output is correct
47	Correct	36 ms	35808 KB	Output is correct
48	Correct	39 ms	36216 KB	Output is correct
49	Correct	43 ms	36320 KB	Output is correct
50	Correct	39 ms	36344 KB	Output is correct
51	Correct	47 ms	36216 KB	Output is correct
52	Correct	39 ms	36216 KB	Output is correct
53	Correct	45 ms	36216 KB	Output is correct
54	Correct	38 ms	36216 KB	Output is correct
55	Correct	42 ms	35704 KB	Output is correct
56	Correct	149 ms	49492 KB	Output is correct
57	Correct	197 ms	49144 KB	Output is correct
58	Correct	38 ms	36264 KB	Output is correct
59	Correct	36 ms	35704 KB	Output is correct
60	Correct	39 ms	35704 KB	Output is correct
61	Correct	234 ms	49124 KB	Output is correct
62	Correct	48 ms	36216 KB	Output is correct
63	Correct	243 ms	56272 KB	Output is correct
64	Correct	250 ms	50296 KB	Output is correct
65	Correct	46 ms	36136 KB	Output is correct
66	Correct	273 ms	51124 KB	Output is correct
67	Correct	38 ms	36216 KB	Output is correct
68	Correct	47 ms	36220 KB	Output is correct
69	Correct	184 ms	50540 KB	Output is correct
70	Correct	61 ms	36472 KB	Output is correct
71	Correct	219 ms	50204 KB	Output is correct
72	Correct	294 ms	52600 KB	Output is correct
73	Correct	37 ms	35704 KB	Output is correct
74	Correct	243 ms	57740 KB	Output is correct
75	Correct	233 ms	54136 KB	Output is correct
76	Correct	46 ms	36212 KB	Output is correct
77	Correct	39 ms	36088 KB	Output is correct
78	Correct	149 ms	49136 KB	Output is correct
79	Correct	185 ms	52348 KB	Output is correct
80	Correct	47 ms	36216 KB	Output is correct
81	Correct	48 ms	36216 KB	Output is correct
82	Correct	36 ms	35704 KB	Output is correct
83	Correct	36 ms	35780 KB	Output is correct
84	Correct	38 ms	36216 KB	Output is correct
85	Correct	240 ms	50436 KB	Output is correct
86	Correct	38 ms	36088 KB	Output is correct
87	Correct	245 ms	49276 KB	Output is correct
88	Correct	36 ms	35704 KB	Output is correct
89	Correct	218 ms	49272 KB	Output is correct
90	Correct	228 ms	50296 KB	Output is correct
91	Correct	218 ms	51908 KB	Output is correct
92	Correct	161 ms	49300 KB	Output is correct
93	Correct	46 ms	36216 KB	Output is correct
94	Correct	41 ms	35704 KB	Output is correct
95	Correct	194 ms	51880 KB	Output is correct
96	Correct	249 ms	55800 KB	Output is correct
97	Correct	39 ms	36216 KB	Output is correct
98	Correct	32 ms	35700 KB	Output is correct
99	Correct	187 ms	50668 KB	Output is correct
100	Correct	38 ms	36216 KB	Output is correct
101	Correct	224 ms	49592 KB	Output is correct
102	Correct	243 ms	54448 KB	Output is correct
103	Correct	38 ms	36216 KB	Output is correct
104	Correct	38 ms	36216 KB	Output is correct
105	Correct	39 ms	36216 KB	Output is correct
106	Correct	37 ms	36216 KB	Output is correct
107	Correct	38 ms	36216 KB	Output is correct
108	Correct	1069 ms	113252 KB	Output is correct
109	Correct	1545 ms	123700 KB	Output is correct
110	Correct	1603 ms	134864 KB	Output is correct
111	Correct	1530 ms	144248 KB	Output is correct
112	Correct	1554 ms	134592 KB	Output is correct
113	Correct	1193 ms	121084 KB	Output is correct
114	Correct	1092 ms	105824 KB	Output is correct
115	Correct	1089 ms	105664 KB	Output is correct
116	Correct	1427 ms	110052 KB	Output is correct
117	Correct	1229 ms	121228 KB	Output is correct
118	Correct	1227 ms	106992 KB	Output is correct
119	Correct	1247 ms	121384 KB	Output is correct
120	Correct	1504 ms	135036 KB	Output is correct
121	Correct	1267 ms	116836 KB	Output is correct
122	Correct	1508 ms	110516 KB	Output is correct
123	Correct	998 ms	119652 KB	Output is correct
124	Correct	1381 ms	119476 KB	Output is correct

답안 #128273

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 24.0 / 24.0

Subtask #3 14.0 / 14.0

Subtask #4 22.0 / 22.0

Subtask #5 30.0 / 30.0

Subtask #1
10.0 / 10.0

Subtask #2
24.0 / 24.0

Subtask #3
14.0 / 14.0

Subtask #4
22.0 / 22.0

Subtask #5
30.0 / 30.0