oj.uz

Submission #122066

# Submission time Handle Problem Language Result Execution time Memory
122066 2019-06-27T13:45:51 Z Rudy420 Mergers (JOI19_mergers) C++17
0 / 100
 120 ms 25120 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],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;
	else if(mn[nod]==h[nod] && gd && nod!=1) fuck++;
	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);
	if(fuck==1) ans++;
	cout << (ans+1)/2;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12288 KB Output is correct
2 Correct 12 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 12 ms 12288 KB Output is correct
11 Correct 12 ms 12288 KB Output is correct
12 Correct 11 ms 12288 KB Output is correct
13 Correct 11 ms 12288 KB Output is correct
14 Correct 11 ms 12288 KB Output is correct
15 Correct 11 ms 12288 KB Output is correct
16 Incorrect 13 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 11 ms 12288 KB Output is correct
2 Correct 12 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 12 ms 12288 KB Output is correct
11 Correct 12 ms 12288 KB Output is correct
12 Correct 11 ms 12288 KB Output is correct
13 Correct 11 ms 12288 KB Output is correct
14 Correct 11 ms 12288 KB Output is correct
15 Correct 11 ms 12288 KB Output is correct
16 Incorrect 13 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 11 ms 12288 KB Output is correct
2 Correct 12 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 12 ms 12288 KB Output is correct
11 Correct 12 ms 12288 KB Output is correct
12 Correct 11 ms 12288 KB Output is correct
13 Correct 11 ms 12288 KB Output is correct
14 Correct 11 ms 12288 KB Output is correct
15 Correct 11 ms 12288 KB Output is correct
16 Incorrect 13 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 120 ms 24748 KB Output is correct
2 Correct 117 ms 25120 KB Output is correct
3 Correct 14 ms 12764 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 11 ms 12288 KB Output is correct
2 Correct 12 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 12 ms 12288 KB Output is correct
11 Correct 12 ms 12288 KB Output is correct
12 Correct 11 ms 12288 KB Output is correct
13 Correct 11 ms 12288 KB Output is correct
14 Correct 11 ms 12288 KB Output is correct
15 Correct 11 ms 12288 KB Output is correct
16 Incorrect 13 ms 12288 KB Output isn't correct
17 Halted 0 ms 0 KB -