oj.uz

Submission #122060

# Submission time Handle Problem Language Result Execution time Memory
122060 2019-06-27T13:31:53 Z Rudy420 Mergers (JOI19_mergers) C++17
0 / 100
 109 ms 25200 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 12 ms 12288 KB Output is correct
2 Correct 11 ms 12288 KB Output is correct
3 Correct 12 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 12 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 11 ms 12288 KB Output is correct
10 Correct 12 ms 12288 KB Output is correct
11 Correct 12 ms 12288 KB Output is correct
12 Correct 12 ms 12288 KB Output is correct
13 Correct 11 ms 12288 KB Output is correct
14 Correct 13 ms 12288 KB Output is correct
15 Correct 11 ms 12288 KB Output is correct
16 Incorrect 11 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 12 ms 12288 KB Output is correct
2 Correct 11 ms 12288 KB Output is correct
3 Correct 12 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 12 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 11 ms 12288 KB Output is correct
10 Correct 12 ms 12288 KB Output is correct
11 Correct 12 ms 12288 KB Output is correct
12 Correct 12 ms 12288 KB Output is correct
13 Correct 11 ms 12288 KB Output is correct
14 Correct 13 ms 12288 KB Output is correct
15 Correct 11 ms 12288 KB Output is correct
16 Incorrect 11 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 12 ms 12288 KB Output is correct
2 Correct 11 ms 12288 KB Output is correct
3 Correct 12 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 12 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 11 ms 12288 KB Output is correct
10 Correct 12 ms 12288 KB Output is correct
11 Correct 12 ms 12288 KB Output is correct
12 Correct 12 ms 12288 KB Output is correct
13 Correct 11 ms 12288 KB Output is correct
14 Correct 13 ms 12288 KB Output is correct
15 Correct 11 ms 12288 KB Output is correct
16 Incorrect 11 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 109 ms 24840 KB Output is correct
2 Incorrect 102 ms 25200 KB Output isn't correct
3 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 11 ms 12288 KB Output is correct
3 Correct 12 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 12 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 11 ms 12288 KB Output is correct
10 Correct 12 ms 12288 KB Output is correct
11 Correct 12 ms 12288 KB Output is correct
12 Correct 12 ms 12288 KB Output is correct
13 Correct 11 ms 12288 KB Output is correct
14 Correct 13 ms 12288 KB Output is correct
15 Correct 11 ms 12288 KB Output is correct
16 Incorrect 11 ms 12288 KB Output isn't correct
17 Halted 0 ms 0 KB -