Submission #122069

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
122069	2019-06-27T13:51:58 Z	Rudy420	Mergers (JOI19_mergers)	C++17	10 / 100	131 ms	25200 KB

mergers

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define ll long long
#define pi pair<int,int>
#define pl pair<ll,ll>
#define pd pair<double,double>
#define ld long double
#define pld pair<ld,ld>
#define lg length()
#define sz size()
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pi>
#define vpl vector<pl>
#define pb push_back
#define INF 1000000005
#define LINF 1000000000000000005
#define eps 0.001
#ifdef LOCAL_DEFINE
    mt19937 rng(69);
#else
    seed_seq seq{
        (uint64_t) chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count(),
        //(uint64_t) __builtin_ia32_rdtsc(),
        //(uint64_t) (uintptr_t) make_unique<char>().get()
    };
    mt19937 rng(seq);
#endif

int n,k,x,y,a[500005],p[20][500005],h[500005],lca[500005],ans,mn[500005],fuck;

vi g[500005];

void DFS1(int nod, int par, int hg){
	h[nod]=hg;
	p[0][nod]=par;
	for(int i=1;i<20;i++){
		p[i][nod]=p[i-1][p[i-1][nod]];
	}
	for(int i : g[nod]){
		if(i!=par){
			DFS1(i,nod,hg+1);
		}
	}
}

int LCA(int x, int y){
	if(h[x]<h[y]) swap(x,y);
	for(int i=19;i>=0;i--){
		if(h[p[i][x]]>=h[y]) x=p[i][x];
	}
	if(x==y) return x;
	for(int i=19;i>=0;i--){
		if(p[i][x]!=p[i][y]) x=p[i][x],y=p[i][x];
	}
	return p[0][x];
}

int DFS2(int nod, int par){
	mn[nod]=h[lca[a[nod]]];
	int gd=0;
	for(int i : g[nod]){
		if(i!=par){
			gd=max(gd,DFS2(i,nod));
			mn[nod]=min(mn[nod],mn[i]);
		}
	}
	if(mn[nod]==h[nod] && !gd && nod!=1) ans++,gd=1;
	return gd;
}

void DFS3(int nod, int par){
	if(mn[nod]==h[nod] && nod!=1){
		fuck++;
		return;
	}
	for(int i : g[nod]){
		if(i!=par){
			DFS3(i,nod);
		}
	}
}

int32_t main(){
#ifdef LOCAL_DEFINE
    ifstream cin("input.txt");
#endif
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin >> n >> k;
    for(int i=1;i<n;i++){
    	cin >> x >> y;
    	g[x].pb(y);
    	g[y].pb(x);
	}
	DFS1(1,1,1);
	for(int i=1;i<=n;i++){
		cin >> a[i];
		if(!lca[a[i]]) lca[a[i]]=i;
		else lca[a[i]]=LCA(lca[a[i]],i);
	}
	DFS2(1,1);
	DFS3(1,1);
	if(fuck==1 && ans%2==0)cout<<ans/2 + 1;
	else cout<<(ans+1)/2;
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	12288 KB	Output is correct
2	Correct	12 ms	12288 KB	Output is correct
3	Correct	16 ms	12288 KB	Output is correct
4	Correct	13 ms	12288 KB	Output is correct
5	Correct	13 ms	12288 KB	Output is correct
6	Correct	12 ms	12288 KB	Output is correct
7	Correct	13 ms	12288 KB	Output is correct
8	Correct	12 ms	12288 KB	Output is correct
9	Correct	16 ms	12288 KB	Output is correct
10	Correct	12 ms	12288 KB	Output is correct
11	Correct	13 ms	12304 KB	Output is correct
12	Correct	12 ms	12288 KB	Output is correct
13	Correct	39 ms	12284 KB	Output is correct
14	Correct	12 ms	12288 KB	Output is correct
15	Correct	12 ms	12288 KB	Output is correct
16	Correct	12 ms	12288 KB	Output is correct
17	Correct	11 ms	12288 KB	Output is correct
18	Correct	12 ms	12288 KB	Output is correct
19	Correct	14 ms	12288 KB	Output is correct
20	Correct	12 ms	12288 KB	Output is correct
21	Correct	12 ms	12288 KB	Output is correct
22	Correct	13 ms	12260 KB	Output is correct
23	Correct	11 ms	12288 KB	Output is correct
24	Correct	11 ms	12288 KB	Output is correct

Subtask #2
0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	12288 KB	Output is correct
2	Correct	12 ms	12288 KB	Output is correct
3	Correct	16 ms	12288 KB	Output is correct
4	Correct	13 ms	12288 KB	Output is correct
5	Correct	13 ms	12288 KB	Output is correct
6	Correct	12 ms	12288 KB	Output is correct
7	Correct	13 ms	12288 KB	Output is correct
8	Correct	12 ms	12288 KB	Output is correct
9	Correct	16 ms	12288 KB	Output is correct
10	Correct	12 ms	12288 KB	Output is correct
11	Correct	13 ms	12304 KB	Output is correct
12	Correct	12 ms	12288 KB	Output is correct
13	Correct	39 ms	12284 KB	Output is correct
14	Correct	12 ms	12288 KB	Output is correct
15	Correct	12 ms	12288 KB	Output is correct
16	Correct	12 ms	12288 KB	Output is correct
17	Correct	11 ms	12288 KB	Output is correct
18	Correct	12 ms	12288 KB	Output is correct
19	Correct	14 ms	12288 KB	Output is correct
20	Correct	12 ms	12288 KB	Output is correct
21	Correct	12 ms	12288 KB	Output is correct
22	Correct	13 ms	12260 KB	Output is correct
23	Correct	11 ms	12288 KB	Output is correct
24	Correct	11 ms	12288 KB	Output is correct
25	Incorrect	12 ms	12288 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Subtask #3
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	12288 KB	Output is correct
2	Correct	12 ms	12288 KB	Output is correct
3	Correct	16 ms	12288 KB	Output is correct
4	Correct	13 ms	12288 KB	Output is correct
5	Correct	13 ms	12288 KB	Output is correct
6	Correct	12 ms	12288 KB	Output is correct
7	Correct	13 ms	12288 KB	Output is correct
8	Correct	12 ms	12288 KB	Output is correct
9	Correct	16 ms	12288 KB	Output is correct
10	Correct	12 ms	12288 KB	Output is correct
11	Correct	13 ms	12304 KB	Output is correct
12	Correct	12 ms	12288 KB	Output is correct
13	Correct	39 ms	12284 KB	Output is correct
14	Correct	12 ms	12288 KB	Output is correct
15	Correct	12 ms	12288 KB	Output is correct
16	Correct	12 ms	12288 KB	Output is correct
17	Correct	11 ms	12288 KB	Output is correct
18	Correct	12 ms	12288 KB	Output is correct
19	Correct	14 ms	12288 KB	Output is correct
20	Correct	12 ms	12288 KB	Output is correct
21	Correct	12 ms	12288 KB	Output is correct
22	Correct	13 ms	12260 KB	Output is correct
23	Correct	11 ms	12288 KB	Output is correct
24	Correct	11 ms	12288 KB	Output is correct
25	Incorrect	11 ms	12288 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Subtask #4
0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	131 ms	24816 KB	Output is correct
2	Correct	97 ms	25200 KB	Output is correct
3	Correct	15 ms	12748 KB	Output is correct
4	Incorrect	14 ms	12672 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	12288 KB	Output is correct
2	Correct	12 ms	12288 KB	Output is correct
3	Correct	16 ms	12288 KB	Output is correct
4	Correct	13 ms	12288 KB	Output is correct
5	Correct	13 ms	12288 KB	Output is correct
6	Correct	12 ms	12288 KB	Output is correct
7	Correct	13 ms	12288 KB	Output is correct
8	Correct	12 ms	12288 KB	Output is correct
9	Correct	16 ms	12288 KB	Output is correct
10	Correct	12 ms	12288 KB	Output is correct
11	Correct	13 ms	12304 KB	Output is correct
12	Correct	12 ms	12288 KB	Output is correct
13	Correct	39 ms	12284 KB	Output is correct
14	Correct	12 ms	12288 KB	Output is correct
15	Correct	12 ms	12288 KB	Output is correct
16	Correct	12 ms	12288 KB	Output is correct
17	Correct	11 ms	12288 KB	Output is correct
18	Correct	12 ms	12288 KB	Output is correct
19	Correct	14 ms	12288 KB	Output is correct
20	Correct	12 ms	12288 KB	Output is correct
21	Correct	12 ms	12288 KB	Output is correct
22	Correct	13 ms	12260 KB	Output is correct
23	Correct	11 ms	12288 KB	Output is correct
24	Correct	11 ms	12288 KB	Output is correct
25	Incorrect	12 ms	12288 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Submission #122069

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 0 / 24.0

Subtask #3 0 / 14.0

Subtask #4 0 / 22.0

Subtask #5 0 / 30.0

Subtask #1
10.0 / 10.0

Subtask #2
0 / 24.0

Subtask #3
0 / 14.0

Subtask #4
0 / 22.0

Subtask #5
0 / 30.0