Submission #249996

#	Time	Username	Problem	Language	Result	Execution time	Memory
249996		Blagojce	Mergers (JOI19_mergers)	C++11	0 / 100	67 ms	22796 KiB

mergers

#include <bits/stdc++.h> 
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

const int i_inf = 1e9;
const ll inf = 1e18;
const ll mod = 1000000007;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;
 
mt19937 _rand(time(NULL));
clock_t timer = clock();
const int mxn = 5e5;
 
const ll A = 911382323;
const ll B = 972663749;
int n, k;
int t[mxn];

int temp_pos = 0;
int pos_to_id[mxn];
int id_to_pos[mxn];
int sz[mxn];
vector<int> g[mxn];

void dfs(int u, int p){
	id_to_pos[u] = temp_pos;
	pos_to_id[temp_pos] = u;
	++temp_pos;
	sz[u] = 1;
	for(auto e : g[u]){
		if(e != p){
			dfs(e, u);
			sz[u] += sz[e];
		}
	}
}
int cnt = 0;
int fi[mxn];
int la[mxn];

pii dfs2(int u, int p){
	int lef = fi[t[u]], rig = la[t[u]];
	for(auto e : g[u]){
		if(e == p) continue;
		pii temp = dfs2(e, u);
		lef = min(lef, temp.st);
		rig = max(rig, temp.nd);
	}
	if(u!=0 && id_to_pos[u] <= lef && rig < id_to_pos[u] + sz[u]){
		
		++cnt;
	}
	return {lef, rig};
	
}

void solve(){
	cin >> n >> k;
	fr(i, 0, n-1){
		int u, v;
		cin >> u >> v;
		--u, --v;
		g[u].pb(v);
		g[v].pb(u);
	}
	fr(i, 0, n){
		cin >> t[i];
	}
	dfs(0, 0);
	
	memset(fi, -1, sizeof(fi));
	memset(la, -1, sizeof(la));
	fr(i, 0, n){
		int curr_id = pos_to_id[i];
		if(fi[t[curr_id]] == -1) fi[t[curr_id]] = i;
		la[t[curr_id]] = i;
	}
	dfs2(0, 0);
	if(cnt <= 1){
		cout<<cnt << endl;
	}
	else{
		cout<<cnt-1<<endl;
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	solve();
	
	
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 24
• Subtask 3: 0 / 14
• Subtask 4: 0 / 22
• Subtask 5: 0 / 30