oj.uz

Submission #138075

# Submission time Handle Problem Language Result Execution time Memory
138075 2019-07-29T09:30:47 Z Mahmoud_Adel Mergers (JOI19_mergers) C++14
0 / 100
 169 ms 72048 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++) 
	{
		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 75 ms 62940 KB Output is correct
2 Correct 57 ms 62968 KB Output is correct
3 Correct 66 ms 62972 KB Output is correct
4 Correct 57 ms 62968 KB Output is correct
5 Correct 65 ms 62968 KB Output is correct
6 Correct 66 ms 62968 KB Output is correct
7 Correct 57 ms 62968 KB Output is correct
8 Correct 58 ms 62968 KB Output is correct
9 Correct 57 ms 62972 KB Output is correct
10 Correct 56 ms 62968 KB Output is correct
11 Correct 57 ms 63096 KB Output is correct
12 Correct 57 ms 62968 KB Output is correct
13 Correct 57 ms 62968 KB Output is correct
14 Correct 57 ms 62916 KB Output is correct
15 Correct 57 ms 63096 KB Output is correct
16 Incorrect 57 ms 62968 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 68568 KB Output is correct
2 Incorrect 169 ms 72048 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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