oj.uz

Submission #138065

# Submission time Handle Problem Language Result Execution time Memory
138065 2019-07-29T09:11:15 Z Mahmoud_Adel Mergers (JOI19_mergers) C++14
0 / 100
 163 ms 72020 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=19; i>=0; 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++) 
	{
		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 56 ms 62972 KB Output is correct
2 Correct 57 ms 62968 KB Output is correct
3 Correct 57 ms 62940 KB Output is correct
4 Correct 57 ms 62968 KB Output is correct
5 Correct 57 ms 62968 KB Output is correct
6 Correct 57 ms 62968 KB Output is correct
7 Correct 57 ms 62940 KB Output is correct
8 Correct 57 ms 62968 KB Output is correct
9 Correct 57 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 62968 KB Output is correct
13 Correct 58 ms 62968 KB Output is correct
14 Correct 56 ms 62968 KB Output is correct
15 Correct 56 ms 62924 KB Output is correct
16 Incorrect 56 ms 63032 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 62972 KB Output is correct
2 Correct 57 ms 62968 KB Output is correct
3 Correct 57 ms 62940 KB Output is correct
4 Correct 57 ms 62968 KB Output is correct
5 Correct 57 ms 62968 KB Output is correct
6 Correct 57 ms 62968 KB Output is correct
7 Correct 57 ms 62940 KB Output is correct
8 Correct 57 ms 62968 KB Output is correct
9 Correct 57 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 62968 KB Output is correct
13 Correct 58 ms 62968 KB Output is correct
14 Correct 56 ms 62968 KB Output is correct
15 Correct 56 ms 62924 KB Output is correct
16 Incorrect 56 ms 63032 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 62972 KB Output is correct
2 Correct 57 ms 62968 KB Output is correct
3 Correct 57 ms 62940 KB Output is correct
4 Correct 57 ms 62968 KB Output is correct
5 Correct 57 ms 62968 KB Output is correct
6 Correct 57 ms 62968 KB Output is correct
7 Correct 57 ms 62940 KB Output is correct
8 Correct 57 ms 62968 KB Output is correct
9 Correct 57 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 62968 KB Output is correct
13 Correct 58 ms 62968 KB Output is correct
14 Correct 56 ms 62968 KB Output is correct
15 Correct 56 ms 62924 KB Output is correct
16 Incorrect 56 ms 63032 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 68640 KB Output is correct
2 Incorrect 163 ms 72020 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 62972 KB Output is correct
2 Correct 57 ms 62968 KB Output is correct
3 Correct 57 ms 62940 KB Output is correct
4 Correct 57 ms 62968 KB Output is correct
5 Correct 57 ms 62968 KB Output is correct
6 Correct 57 ms 62968 KB Output is correct
7 Correct 57 ms 62940 KB Output is correct
8 Correct 57 ms 62968 KB Output is correct
9 Correct 57 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 62968 KB Output is correct
13 Correct 58 ms 62968 KB Output is correct
14 Correct 56 ms 62968 KB Output is correct
15 Correct 56 ms 62924 KB Output is correct
16 Incorrect 56 ms 63032 KB Output isn't correct
17 Halted 0 ms 0 KB -