Submission #554117

#	Time	Username	Problem	Language	Result	Execution time	Memory
554117		MilosMilutinovic	Mergers (JOI19_mergers)	C++14	100 / 100	1525 ms	133724 KiB

mergers

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=500050;
int n,k,dep[N],cc[N],deg[N];
VI g[N],v[N];

#define LOG 20
int par[N][LOG];
void dfs1(int u,int p) {
	dep[u]=dep[p]+1;
	par[u][0]=p;
	rep(i,1,LOG) par[u][i]=par[par[u][i-1]][i-1];
	for (int v:g[u]) if (v!=p) dfs1(v,u);
}

int lca(int u,int v) {
	if (dep[u]>dep[v]) swap(u,v);
	per(i,0,LOG) if (dep[par[v][i]]>=dep[u]) v=par[v][i];
	if (u==v) return u;
	per(i,0,LOG) if (par[v][i]!=par[u][i]) v=par[v][i],u=par[u][i];
	return par[v][0];
}

void dfs2(int u,int p) {
	for (int v:g[u])
		if (v!=p) {
			dfs2(v,u);
			cc[u]+=cc[v];
		}
}

void solve(int u,int p,int prv) {
	for (int v:g[u]) {
		if (v==p) continue;
		if (cc[v]==0) {
			deg[v]++; deg[prv]++;
			solve(v,u,v);
		} else {
			solve(v,u,prv);
		}
	}
}

int main() {
	scanf("%d%d",&n,&k);
	rep(i,1,n) {
		int u,v;
		scanf("%d%d",&u,&v);
		g[u].pb(v);
		g[v].pb(u);
	}
	rep(i,1,n+1) {
		int s;
		scanf("%d",&s);
		v[s].pb(i);
	}
	dfs1(1,0);
	rep(i,1,k+1) rep(j,1,v[i].size()) {
		cc[v[i][j]]++;
		cc[v[i][j-1]]++;
		cc[lca(v[i][j],v[i][j-1])]-=2;
	}
	dfs2(1,0);
	solve(1,0,1);
	int cnt=0;
	rep(i,1,n+1) if (deg[i]==1) cnt++;
	printf("%d",(cnt+1)/2);
	return 0;
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:3:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define rep(i,a,n) for (int i=a;i<n;i++)
......
   77 |  rep(i,1,k+1) rep(j,1,v[i].size()) {
      |                   ~~~~~~~~~~~~~~~ 
mergers.cpp:77:15: note: in expansion of macro 'rep'
   77 |  rep(i,1,k+1) rep(j,1,v[i].size()) {
      |               ^~~
mergers.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |  scanf("%d%d",&n,&k);
      |  ~~~~~^~~~~~~~~~~~~~
mergers.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |   scanf("%d%d",&u,&v);
      |   ~~~~~^~~~~~~~~~~~~~
mergers.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |   scanf("%d",&s);
      |   ~~~~~^~~~~~~~~

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