oj.uz

Submission #122065

# Submission time Handle Problem Language Result Execution time Memory
122065 2019-06-27T13:41:43 Z Rudy420 Mergers (JOI19_mergers) C++14
0 / 100
 117 ms 25164 KB 
#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];

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;
}

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);
	cout << (ans+1)/2;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12288 KB Output is correct
2 Correct 13 ms 12288 KB Output is correct
3 Correct 13 ms 12288 KB Output is correct
4 Correct 12 ms 12288 KB Output is correct
5 Correct 11 ms 12288 KB Output is correct
6 Correct 13 ms 12288 KB Output is correct
7 Correct 12 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 12 ms 12288 KB Output is correct
11 Correct 13 ms 12288 KB Output is correct
12 Correct 12 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 Incorrect 12 ms 12288 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12288 KB Output is correct
2 Correct 13 ms 12288 KB Output is correct
3 Correct 13 ms 12288 KB Output is correct
4 Correct 12 ms 12288 KB Output is correct
5 Correct 11 ms 12288 KB Output is correct
6 Correct 13 ms 12288 KB Output is correct
7 Correct 12 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 12 ms 12288 KB Output is correct
11 Correct 13 ms 12288 KB Output is correct
12 Correct 12 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 Incorrect 12 ms 12288 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12288 KB Output is correct
2 Correct 13 ms 12288 KB Output is correct
3 Correct 13 ms 12288 KB Output is correct
4 Correct 12 ms 12288 KB Output is correct
5 Correct 11 ms 12288 KB Output is correct
6 Correct 13 ms 12288 KB Output is correct
7 Correct 12 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 12 ms 12288 KB Output is correct
11 Correct 13 ms 12288 KB Output is correct
12 Correct 12 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 Incorrect 12 ms 12288 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 24736 KB Output is correct
2 Incorrect 106 ms 25164 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12288 KB Output is correct
2 Correct 13 ms 12288 KB Output is correct
3 Correct 13 ms 12288 KB Output is correct
4 Correct 12 ms 12288 KB Output is correct
5 Correct 11 ms 12288 KB Output is correct
6 Correct 13 ms 12288 KB Output is correct
7 Correct 12 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 12 ms 12288 KB Output is correct
11 Correct 13 ms 12288 KB Output is correct
12 Correct 12 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 Incorrect 12 ms 12288 KB Output isn't correct
17 Halted 0 ms 0 KB -