oj.uz

Submission #138076

# Submission time Handle Problem Language Result Execution time Memory
138076 2019-07-29T09:35:41 Z Mahmoud_Adel Mergers (JOI19_mergers) C++14
0 / 100
 168 ms 71928 KB 
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
typedef long long ll;
const int N = 5e5+5;
int n, m, cnt, s[N], dep[N], sp[N][20], sub[N], ret[N], mark[N], acc[N];
vector<int> adj[N], vec[N];
void pre(int u, int p)
{
	sub[u] = 1;
	dep[u] = dep[p]+1;
	sp[u][0] = p;
	for(int i=1; i<20; i++) sp[u][i] = sp[sp[u][i-1]][i-1];
	for(int v : adj[u]) if(v != p) pre(v, u), sub[u] += sub[v];	
}	
int equate(int u, int v)
{
	int c = dep[u]-dep[v];
	for(int i=0; i<20; i++) if(c & (1<<i)) u = sp[u][i];
	return u;
}
int LCA(int u, int v)
{
	if(dep[u] < dep[v]) swap(u, v);
	u = equate(u, v);
	if(u == v) return u;
	for(int i=19; i>=0; i--) if(sp[u][i] != sp[v][i]) u = sp[u][i], v = sp[v][i];
	return sp[u][0];
}
void calc(int u, int p)
{
	for(auto v : adj[u]) if(v != p) calc(v, u), ret[u] += ret[v];
	if(ret[u] == sub[u]) mark[u] = 1;
}
void DFS(int u, int p)
{
	for(auto v : adj[u]) if(v != p) DFS(v, u), acc[u] += acc[v];
	if(mark[u] && !acc[u]) cnt++;
	acc[u] += mark[u];
}
int main()
{
	scanf("%d %d", &n, &m);
	memset(sp, -1, sizeof sp);
	for(int i=1, a, b; i<n; i++) scanf("%d %d", &a, &b),
	adj[a].push_back(b), adj[b].push_back(a);
	for(int i=1; i<=n; i++) scanf("%d", &s[i]), vec[s[i]].push_back(i);
	pre(1, 0);
	for(int i=1; i<=m; i++) 
	{
		if(vec[i].empty()) continue;
		int node = vec[i][0];
		for(auto u : vec[i]) node = LCA(node, u);
		ret[node] += vec[i].size();
	}
	calc(1, 0);
	mark[1] = 0;
	DFS(1, 0);
	cout << (cnt+1)/2 << endl;
}

Compilation message

mergers.cpp: In function 'int main()':
mergers.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:47:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1, a, b; i<n; i++) scanf("%d %d", &a, &b),
                               ~~~~~~~~~~~~~~~~~~~~~~~~
  adj[a].push_back(b), adj[b].push_back(a);
  ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
mergers.cpp:48:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=n; i++) scanf("%d", &s[i]), vec[s[i]].push_back(i);
                          ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 62972 KB Output is correct
2 Correct 57 ms 62968 KB Output is correct
3 Correct 57 ms 62968 KB Output is correct
4 Correct 57 ms 62968 KB Output is correct
5 Correct 57 ms 62840 KB Output is correct
6 Correct 57 ms 63024 KB Output is correct
7 Correct 56 ms 63096 KB Output is correct
8 Correct 56 ms 62976 KB Output is correct
9 Correct 58 ms 62968 KB Output is correct
10 Correct 57 ms 62968 KB Output is correct
11 Correct 57 ms 62968 KB Output is correct
12 Correct 57 ms 63096 KB Output is correct
13 Correct 57 ms 62968 KB Output is correct
14 Correct 57 ms 62968 KB Output is correct
15 Correct 57 ms 63096 KB Output is correct
16 Incorrect 57 ms 62984 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 62972 KB Output is correct
2 Correct 57 ms 62968 KB Output is correct
3 Correct 57 ms 62968 KB Output is correct
4 Correct 57 ms 62968 KB Output is correct
5 Correct 57 ms 62840 KB Output is correct
6 Correct 57 ms 63024 KB Output is correct
7 Correct 56 ms 63096 KB Output is correct
8 Correct 56 ms 62976 KB Output is correct
9 Correct 58 ms 62968 KB Output is correct
10 Correct 57 ms 62968 KB Output is correct
11 Correct 57 ms 62968 KB Output is correct
12 Correct 57 ms 63096 KB Output is correct
13 Correct 57 ms 62968 KB Output is correct
14 Correct 57 ms 62968 KB Output is correct
15 Correct 57 ms 63096 KB Output is correct
16 Incorrect 57 ms 62984 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 62972 KB Output is correct
2 Correct 57 ms 62968 KB Output is correct
3 Correct 57 ms 62968 KB Output is correct
4 Correct 57 ms 62968 KB Output is correct
5 Correct 57 ms 62840 KB Output is correct
6 Correct 57 ms 63024 KB Output is correct
7 Correct 56 ms 63096 KB Output is correct
8 Correct 56 ms 62976 KB Output is correct
9 Correct 58 ms 62968 KB Output is correct
10 Correct 57 ms 62968 KB Output is correct
11 Correct 57 ms 62968 KB Output is correct
12 Correct 57 ms 63096 KB Output is correct
13 Correct 57 ms 62968 KB Output is correct
14 Correct 57 ms 62968 KB Output is correct
15 Correct 57 ms 63096 KB Output is correct
16 Incorrect 57 ms 62984 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 68592 KB Output is correct
2 Incorrect 168 ms 71928 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 62972 KB Output is correct
2 Correct 57 ms 62968 KB Output is correct
3 Correct 57 ms 62968 KB Output is correct
4 Correct 57 ms 62968 KB Output is correct
5 Correct 57 ms 62840 KB Output is correct
6 Correct 57 ms 63024 KB Output is correct
7 Correct 56 ms 63096 KB Output is correct
8 Correct 56 ms 62976 KB Output is correct
9 Correct 58 ms 62968 KB Output is correct
10 Correct 57 ms 62968 KB Output is correct
11 Correct 57 ms 62968 KB Output is correct
12 Correct 57 ms 63096 KB Output is correct
13 Correct 57 ms 62968 KB Output is correct
14 Correct 57 ms 62968 KB Output is correct
15 Correct 57 ms 63096 KB Output is correct
16 Incorrect 57 ms 62984 KB Output isn't correct
17 Halted 0 ms 0 KB -