Submission #129772

#	Time	Username	Problem	Language	Result	Execution time	Memory
129772		dndhk	Mergers (JOI19_mergers)	C++14	0 / 100	167 ms	43236 KiB

mergers

#include <bits/stdc++.h>

#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL


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

const int MAX_N = 500000;
const int MAX_T = 20;

int N, K;
vector<int> gp[MAX_N+1];
int p[MAX_N+1][20];
int par[MAX_N+1];
int in[MAX_N+1], out[MAX_N+1], cnt = 0;
int lv[MAX_N+1];

void dfs(int x){
	in[x] = ++cnt;
	par[x] = p[x][0];
	for(int j=1; j<MAX_T; j++){
		p[x][j] = p[p[x][j-1]][j-1];
	}
	for(int i=0; i<gp[x].size(); i++){
		if(gp[x][i]==p[x][0])	continue;
		p[gp[x][i]][0] = x;
		lv[gp[x][i]] = lv[x]+1;
		dfs(gp[x][i]);
	}
	out[x] = cnt;
}
vector<int> st[MAX_N+1];

bool sf(int x, int y){
	return in[x]<in[y];
}

int lca(int x, int y){
	for(int i=MAX_T-1; i>=0; i--){
		if(lv[p[x][i]]>=lv[y]){
			x = p[x][i];
		}if(lv[p[y][i]]>=lv[x]){
			y = p[x][i];
		}
	}
	for(int i=MAX_T-1; i>=0; i--){
		if(p[x][i]!=p[y][i]){
			x = p[x][i]; y = p[y][i];
		}
	}
	if(x!=y){
		x = p[x][0];
	}
	return x;
}

vector<pii> upd;

int g[MAX_N+1];

void init_g(int x){
	for(int i=1; i<=x; i++){
		g[i] = i;
	}
}

int find_g(int x){
	return (x==g[x]) ? x : g[x] = find_g(g[x]);
}

void union_g(int x, int y){
	x = find_g(x); y = find_g(y);
	g[x] = y;
}

void merge_g(int x, int y){
	if(lv[x]<=lv[y])	return;
	merge_g(par[x], y); par[x] = y;
	union_g(x, y);
}

vector<pii> edge;
int degree[MAX_N+1];

int main(){
	scanf("%d%d", &N, &K);
	init_g(N);
	for(int i=0; i<N-1; i++){
		int a, b;
		scanf("%d%d", &a, &b);
		gp[a].pb(b); gp[b].pb(a);
		edge.pb({a, b});
	}
	lv[1] = 1;
	dfs(1);
	for(int i=1; i<=N; i++){
		int x;
		scanf("%d", &x);
		st[x].pb(i);
	}
	for(int i=1; i<=K; i++){
		sort(st[i].begin(), st[i].end(), sf);
		for(int j=1; j<st[i].size(); j++){
			int x = st[i][j-1]; int y = st[i][j];
			upd.pb({x, lca(x, y)}); upd.pb({y, lca(x, y)});
		}
	}
	while(!upd.empty()){
		int x = upd.back().first; int y = upd.back().second; upd.pop_back();
		merge_g(x, y);
	}
	for(int i=0; i<edge.size(); i++){
		if(find_g(edge[i].first) != find_g(edge[i].second)){
			degree[find_g(edge[i].first)]++; degree[find_g(edge[i].second)]++;
		}
	}
	int ans = 0;
	for(int i=1; i<=N; i++){
		if(degree[i]==1)	ans++;
	}
	printf("%d", (ans+1)/2);
	return 0;
}

Compilation message (stderr)

mergers.cpp: In function 'void dfs(int)':
mergers.cpp:40:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<gp[x].size(); i++){
               ~^~~~~~~~~~~~~
mergers.cpp: In function 'int main()':
mergers.cpp:119:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=1; j<st[i].size(); j++){
                ~^~~~~~~~~~~~~
mergers.cpp:128:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<edge.size(); i++){
               ~^~~~~~~~~~~~
mergers.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &K);
  ~~~~~^~~~~~~~~~~~~~~~
mergers.cpp:106:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
mergers.cpp:114:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~

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