oj.uz

Submission #200387

# Submission time Handle Problem Language Result Execution time Memory
200387 2020-02-06T14:09:31 Z arnold518 Mergers (JOI19_mergers) C++14
0 / 100
 142 ms 45300 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 5e5;

int N, K;
vector<int> adj[MAXN+10], A[MAXN+10];
int par[MAXN+10][30], dep[MAXN+10];

void dfs(int now, int bef, int d)
{	
	par[now][0]=bef; dep[now]=d;
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		dfs(nxt, now, d+1);
	}
}

int lca(int u, int v)
{
	int i, j;
	if(dep[u]>dep[v]) swap(u, v);
	for(i=20; i>=0; i--) if(dep[par[v][i]]>=dep[u]) v=par[v][i];
	if(u==v) return u;
	for(i=20; i>=0; i--) if(par[v][i]!=par[u][i]) v=par[v][i], u=par[u][i];
	return par[u][0];
}

int B[MAXN+10], ppar[MAXN+10], cnt[MAXN+10], ans;

int Find(int x) { return x==ppar[x] ? x : ppar[x]=Find(ppar[x]); }
void Union(int x, int y) { x=Find(x); y=Find(y); ppar[x]=y; }

void dfs2(int now, int bef)
{
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		dfs2(nxt, now);
		B[now]+=B[nxt];
	}
	if(now!=bef && B[now]) Union(now, bef);
}

int main()
{
	int i, j;

	scanf("%d%d", &N, &K);
	for(i=1; i<=N; i++) ppar[i]=i;
	for(i=1; i<N; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for(i=1; i<=N; i++)
	{
		int t;
		scanf("%d", &t);
		A[t].push_back(i);
	}

	dfs(1, 1, 1);
	for(i=1; i<=20; i++) for(j=1; j<=N; j++) par[j][i]=par[par[j][i-1]][i-1];

	for(i=1; i<=K; i++)
	{
		for(j=1; j<A[i].size(); j++)
		{
			int u=A[i][j-1], v=A[i][j], w=lca(u, v);
			B[u]++; B[v]++; B[w]--; B[w]--;
		}
	}

	dfs2(1, 1);
	for(i=2; i<=N; i++)
	{
		int u=i, v=par[u][0];
		cnt[Find(u)]++; cnt[Find(v)]++;
	}

	for(i=1; i<=N; i++) if(cnt[i]==1) ans++;
	ans++; ans/=2;
	printf("%d", ans);
}

Compilation message

mergers.cpp: In function 'int lca(int, int)':
mergers.cpp:26:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
mergers.cpp: In function 'int main()':
mergers.cpp:75:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=1; j<A[i].size(); j++)
            ~^~~~~~~~~~~~
mergers.cpp:54: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:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~
mergers.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t);
   ~~~~~^~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23800 KB Output is correct
2 Incorrect 19 ms 23800 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23800 KB Output is correct
2 Incorrect 19 ms 23800 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23800 KB Output is correct
2 Incorrect 19 ms 23800 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 42328 KB Output is correct
2 Correct 131 ms 45300 KB Output is correct
3 Incorrect 23 ms 24440 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23800 KB Output is correct
2 Incorrect 19 ms 23800 KB Output isn't correct
3 Halted 0 ms 0 KB -