답안 #128268

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
128268	2019-07-10T15:43:58 Z	mohammedehab2002	Mergers (JOI19_mergers)	C++11	56 / 100	3000 ms	57612 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 (u!=v)
	{
		Union(u,dp[0][u]);
		u=dp[0][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	35 ms	35704 KB	Output is correct
2	Correct	35 ms	35704 KB	Output is correct
3	Correct	35 ms	35704 KB	Output is correct
4	Correct	36 ms	35736 KB	Output is correct
5	Correct	36 ms	35704 KB	Output is correct
6	Correct	36 ms	35704 KB	Output is correct
7	Correct	36 ms	35704 KB	Output is correct
8	Correct	35 ms	35704 KB	Output is correct
9	Correct	35 ms	35768 KB	Output is correct
10	Correct	36 ms	35704 KB	Output is correct
11	Correct	35 ms	35576 KB	Output is correct
12	Correct	36 ms	35704 KB	Output is correct
13	Correct	31 ms	35832 KB	Output is correct
14	Correct	35 ms	35704 KB	Output is correct
15	Correct	36 ms	35704 KB	Output is correct
16	Correct	38 ms	35820 KB	Output is correct
17	Correct	36 ms	35752 KB	Output is correct
18	Correct	36 ms	35704 KB	Output is correct
19	Correct	37 ms	35704 KB	Output is correct
20	Correct	36 ms	35708 KB	Output is correct
21	Correct	37 ms	35704 KB	Output is correct
22	Correct	36 ms	35704 KB	Output is correct
23	Correct	36 ms	35700 KB	Output is correct
24	Correct	51 ms	35704 KB	Output is correct

Subtask #2

24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	35704 KB	Output is correct
2	Correct	35 ms	35704 KB	Output is correct
3	Correct	35 ms	35704 KB	Output is correct
4	Correct	36 ms	35736 KB	Output is correct
5	Correct	36 ms	35704 KB	Output is correct
6	Correct	36 ms	35704 KB	Output is correct
7	Correct	36 ms	35704 KB	Output is correct
8	Correct	35 ms	35704 KB	Output is correct
9	Correct	35 ms	35768 KB	Output is correct
10	Correct	36 ms	35704 KB	Output is correct
11	Correct	35 ms	35576 KB	Output is correct
12	Correct	36 ms	35704 KB	Output is correct
13	Correct	31 ms	35832 KB	Output is correct
14	Correct	35 ms	35704 KB	Output is correct
15	Correct	36 ms	35704 KB	Output is correct
16	Correct	38 ms	35820 KB	Output is correct
17	Correct	36 ms	35752 KB	Output is correct
18	Correct	36 ms	35704 KB	Output is correct
19	Correct	37 ms	35704 KB	Output is correct
20	Correct	36 ms	35708 KB	Output is correct
21	Correct	37 ms	35704 KB	Output is correct
22	Correct	36 ms	35704 KB	Output is correct
23	Correct	36 ms	35700 KB	Output is correct
24	Correct	51 ms	35704 KB	Output is correct
25	Correct	36 ms	35704 KB	Output is correct
26	Correct	39 ms	36216 KB	Output is correct
27	Correct	38 ms	36344 KB	Output is correct
28	Correct	39 ms	36344 KB	Output is correct
29	Correct	39 ms	36216 KB	Output is correct
30	Correct	39 ms	36216 KB	Output is correct
31	Correct	43 ms	35704 KB	Output is correct
32	Correct	40 ms	36472 KB	Output is correct
33	Correct	36 ms	35704 KB	Output is correct
34	Correct	38 ms	36216 KB	Output is correct
35	Correct	38 ms	36216 KB	Output is correct
36	Correct	43 ms	36216 KB	Output is correct
37	Correct	38 ms	36216 KB	Output is correct
38	Correct	36 ms	35704 KB	Output is correct
39	Correct	39 ms	36088 KB	Output is correct
40	Correct	39 ms	36216 KB	Output is correct
41	Correct	39 ms	36160 KB	Output is correct
42	Correct	39 ms	36216 KB	Output is correct
43	Correct	79 ms	36476 KB	Output is correct
44	Correct	35 ms	35704 KB	Output is correct
45	Correct	48 ms	36216 KB	Output is correct
46	Correct	39 ms	36192 KB	Output is correct
47	Correct	36 ms	35704 KB	Output is correct
48	Correct	39 ms	36216 KB	Output is correct
49	Correct	39 ms	36344 KB	Output is correct
50	Correct	39 ms	36344 KB	Output is correct
51	Correct	39 ms	36220 KB	Output is correct
52	Correct	38 ms	36216 KB	Output is correct
53	Correct	40 ms	36344 KB	Output is correct
54	Correct	39 ms	36084 KB	Output is correct

Subtask #3

0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	35704 KB	Output is correct
2	Correct	35 ms	35704 KB	Output is correct
3	Correct	35 ms	35704 KB	Output is correct
4	Correct	36 ms	35736 KB	Output is correct
5	Correct	36 ms	35704 KB	Output is correct
6	Correct	36 ms	35704 KB	Output is correct
7	Correct	36 ms	35704 KB	Output is correct
8	Correct	35 ms	35704 KB	Output is correct
9	Correct	35 ms	35768 KB	Output is correct
10	Correct	36 ms	35704 KB	Output is correct
11	Correct	35 ms	35576 KB	Output is correct
12	Correct	36 ms	35704 KB	Output is correct
13	Correct	31 ms	35832 KB	Output is correct
14	Correct	35 ms	35704 KB	Output is correct
15	Correct	36 ms	35704 KB	Output is correct
16	Correct	38 ms	35820 KB	Output is correct
17	Correct	36 ms	35752 KB	Output is correct
18	Correct	36 ms	35704 KB	Output is correct
19	Correct	37 ms	35704 KB	Output is correct
20	Correct	36 ms	35708 KB	Output is correct
21	Correct	37 ms	35704 KB	Output is correct
22	Correct	36 ms	35704 KB	Output is correct
23	Correct	36 ms	35700 KB	Output is correct
24	Correct	51 ms	35704 KB	Output is correct
25	Correct	37 ms	35960 KB	Output is correct
26	Correct	151 ms	50200 KB	Output is correct
27	Correct	216 ms	49656 KB	Output is correct
28	Correct	39 ms	36216 KB	Output is correct
29	Correct	36 ms	35704 KB	Output is correct
30	Correct	35 ms	35704 KB	Output is correct
31	Correct	227 ms	50556 KB	Output is correct
32	Correct	40 ms	36224 KB	Output is correct
33	Execution timed out	3089 ms	54364 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-

Subtask #4

22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	149 ms	49248 KB	Output is correct
2	Correct	178 ms	52200 KB	Output is correct
3	Correct	38 ms	36216 KB	Output is correct
4	Correct	40 ms	36216 KB	Output is correct
5	Correct	42 ms	35704 KB	Output is correct
6	Correct	35 ms	35704 KB	Output is correct
7	Correct	44 ms	36216 KB	Output is correct
8	Correct	239 ms	51192 KB	Output is correct
9	Correct	38 ms	36088 KB	Output is correct
10	Correct	217 ms	50860 KB	Output is correct
11	Correct	35 ms	35676 KB	Output is correct
12	Correct	284 ms	50792 KB	Output is correct
13	Correct	232 ms	52116 KB	Output is correct
14	Correct	214 ms	52712 KB	Output is correct
15	Correct	149 ms	49648 KB	Output is correct
16	Correct	38 ms	36216 KB	Output is correct
17	Correct	37 ms	35704 KB	Output is correct
18	Correct	192 ms	53616 KB	Output is correct
19	Correct	244 ms	57612 KB	Output is correct
20	Correct	40 ms	36376 KB	Output is correct
21	Correct	35 ms	35728 KB	Output is correct
22	Correct	189 ms	52276 KB	Output is correct
23	Correct	39 ms	36272 KB	Output is correct
24	Correct	235 ms	51400 KB	Output is correct
25	Correct	236 ms	56184 KB	Output is correct
26	Correct	44 ms	36204 KB	Output is correct
27	Correct	46 ms	36388 KB	Output is correct
28	Correct	49 ms	36216 KB	Output is correct
29	Correct	52 ms	36120 KB	Output is correct
30	Correct	47 ms	36404 KB	Output is correct

Subtask #5

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	35704 KB	Output is correct
2	Correct	35 ms	35704 KB	Output is correct
3	Correct	35 ms	35704 KB	Output is correct
4	Correct	36 ms	35736 KB	Output is correct
5	Correct	36 ms	35704 KB	Output is correct
6	Correct	36 ms	35704 KB	Output is correct
7	Correct	36 ms	35704 KB	Output is correct
8	Correct	35 ms	35704 KB	Output is correct
9	Correct	35 ms	35768 KB	Output is correct
10	Correct	36 ms	35704 KB	Output is correct
11	Correct	35 ms	35576 KB	Output is correct
12	Correct	36 ms	35704 KB	Output is correct
13	Correct	31 ms	35832 KB	Output is correct
14	Correct	35 ms	35704 KB	Output is correct
15	Correct	36 ms	35704 KB	Output is correct
16	Correct	38 ms	35820 KB	Output is correct
17	Correct	36 ms	35752 KB	Output is correct
18	Correct	36 ms	35704 KB	Output is correct
19	Correct	37 ms	35704 KB	Output is correct
20	Correct	36 ms	35708 KB	Output is correct
21	Correct	37 ms	35704 KB	Output is correct
22	Correct	36 ms	35704 KB	Output is correct
23	Correct	36 ms	35700 KB	Output is correct
24	Correct	51 ms	35704 KB	Output is correct
25	Correct	36 ms	35704 KB	Output is correct
26	Correct	39 ms	36216 KB	Output is correct
27	Correct	38 ms	36344 KB	Output is correct
28	Correct	39 ms	36344 KB	Output is correct
29	Correct	39 ms	36216 KB	Output is correct
30	Correct	39 ms	36216 KB	Output is correct
31	Correct	43 ms	35704 KB	Output is correct
32	Correct	40 ms	36472 KB	Output is correct
33	Correct	36 ms	35704 KB	Output is correct
34	Correct	38 ms	36216 KB	Output is correct
35	Correct	38 ms	36216 KB	Output is correct
36	Correct	43 ms	36216 KB	Output is correct
37	Correct	38 ms	36216 KB	Output is correct
38	Correct	36 ms	35704 KB	Output is correct
39	Correct	39 ms	36088 KB	Output is correct
40	Correct	39 ms	36216 KB	Output is correct
41	Correct	39 ms	36160 KB	Output is correct
42	Correct	39 ms	36216 KB	Output is correct
43	Correct	79 ms	36476 KB	Output is correct
44	Correct	35 ms	35704 KB	Output is correct
45	Correct	48 ms	36216 KB	Output is correct
46	Correct	39 ms	36192 KB	Output is correct
47	Correct	36 ms	35704 KB	Output is correct
48	Correct	39 ms	36216 KB	Output is correct
49	Correct	39 ms	36344 KB	Output is correct
50	Correct	39 ms	36344 KB	Output is correct
51	Correct	39 ms	36220 KB	Output is correct
52	Correct	38 ms	36216 KB	Output is correct
53	Correct	40 ms	36344 KB	Output is correct
54	Correct	39 ms	36084 KB	Output is correct
55	Correct	37 ms	35960 KB	Output is correct
56	Correct	151 ms	50200 KB	Output is correct
57	Correct	216 ms	49656 KB	Output is correct
58	Correct	39 ms	36216 KB	Output is correct
59	Correct	36 ms	35704 KB	Output is correct
60	Correct	35 ms	35704 KB	Output is correct
61	Correct	227 ms	50556 KB	Output is correct
62	Correct	40 ms	36224 KB	Output is correct
63	Execution timed out	3089 ms	54364 KB	Time limit exceeded
64	Halted	0 ms	0 KB	-