Submission #122068

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
122068	2019-06-27T13:49:35 Z	Rudy420	Mergers (JOI19_mergers)	C++17	10 / 100	126 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++;
	cout << (ans+1)/2;
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	12232 KB	Output is correct
2	Correct	11 ms	12288 KB	Output is correct
3	Correct	11 ms	12288 KB	Output is correct
4	Correct	12 ms	12288 KB	Output is correct
5	Correct	12 ms	12288 KB	Output is correct
6	Correct	11 ms	12288 KB	Output is correct
7	Correct	11 ms	12288 KB	Output is correct
8	Correct	12 ms	12288 KB	Output is correct
9	Correct	12 ms	12288 KB	Output is correct
10	Correct	11 ms	12288 KB	Output is correct
11	Correct	13 ms	12288 KB	Output is correct
12	Correct	13 ms	12288 KB	Output is correct
13	Correct	12 ms	12288 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	12 ms	12288 KB	Output is correct
18	Correct	11 ms	12288 KB	Output is correct
19	Correct	11 ms	12288 KB	Output is correct
20	Correct	11 ms	12288 KB	Output is correct
21	Correct	13 ms	12288 KB	Output is correct
22	Correct	10 ms	12288 KB	Output is correct
23	Correct	13 ms	12288 KB	Output is correct
24	Correct	12 ms	12260 KB	Output is correct

Subtask #2
0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	12232 KB	Output is correct
2	Correct	11 ms	12288 KB	Output is correct
3	Correct	11 ms	12288 KB	Output is correct
4	Correct	12 ms	12288 KB	Output is correct
5	Correct	12 ms	12288 KB	Output is correct
6	Correct	11 ms	12288 KB	Output is correct
7	Correct	11 ms	12288 KB	Output is correct
8	Correct	12 ms	12288 KB	Output is correct
9	Correct	12 ms	12288 KB	Output is correct
10	Correct	11 ms	12288 KB	Output is correct
11	Correct	13 ms	12288 KB	Output is correct
12	Correct	13 ms	12288 KB	Output is correct
13	Correct	12 ms	12288 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	12 ms	12288 KB	Output is correct
18	Correct	11 ms	12288 KB	Output is correct
19	Correct	11 ms	12288 KB	Output is correct
20	Correct	11 ms	12288 KB	Output is correct
21	Correct	13 ms	12288 KB	Output is correct
22	Correct	10 ms	12288 KB	Output is correct
23	Correct	13 ms	12288 KB	Output is correct
24	Correct	12 ms	12260 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	12232 KB	Output is correct
2	Correct	11 ms	12288 KB	Output is correct
3	Correct	11 ms	12288 KB	Output is correct
4	Correct	12 ms	12288 KB	Output is correct
5	Correct	12 ms	12288 KB	Output is correct
6	Correct	11 ms	12288 KB	Output is correct
7	Correct	11 ms	12288 KB	Output is correct
8	Correct	12 ms	12288 KB	Output is correct
9	Correct	12 ms	12288 KB	Output is correct
10	Correct	11 ms	12288 KB	Output is correct
11	Correct	13 ms	12288 KB	Output is correct
12	Correct	13 ms	12288 KB	Output is correct
13	Correct	12 ms	12288 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	12 ms	12288 KB	Output is correct
18	Correct	11 ms	12288 KB	Output is correct
19	Correct	11 ms	12288 KB	Output is correct
20	Correct	11 ms	12288 KB	Output is correct
21	Correct	13 ms	12288 KB	Output is correct
22	Correct	10 ms	12288 KB	Output is correct
23	Correct	13 ms	12288 KB	Output is correct
24	Correct	12 ms	12260 KB	Output is correct
25	Incorrect	13 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	126 ms	24832 KB	Output is correct
2	Correct	118 ms	25200 KB	Output is correct
3	Correct	14 ms	12672 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	12232 KB	Output is correct
2	Correct	11 ms	12288 KB	Output is correct
3	Correct	11 ms	12288 KB	Output is correct
4	Correct	12 ms	12288 KB	Output is correct
5	Correct	12 ms	12288 KB	Output is correct
6	Correct	11 ms	12288 KB	Output is correct
7	Correct	11 ms	12288 KB	Output is correct
8	Correct	12 ms	12288 KB	Output is correct
9	Correct	12 ms	12288 KB	Output is correct
10	Correct	11 ms	12288 KB	Output is correct
11	Correct	13 ms	12288 KB	Output is correct
12	Correct	13 ms	12288 KB	Output is correct
13	Correct	12 ms	12288 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	12 ms	12288 KB	Output is correct
18	Correct	11 ms	12288 KB	Output is correct
19	Correct	11 ms	12288 KB	Output is correct
20	Correct	11 ms	12288 KB	Output is correct
21	Correct	13 ms	12288 KB	Output is correct
22	Correct	10 ms	12288 KB	Output is correct
23	Correct	13 ms	12288 KB	Output is correct
24	Correct	12 ms	12260 KB	Output is correct
25	Incorrect	12 ms	12288 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Submission #122068

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