oj.uz

Submission #138071

# Submission time Handle Problem Language Result Execution time Memory
138071 2019-07-29T09:15:54 Z Mahmoud_Adel Mergers (JOI19_mergers) C++14
0 / 100
 161 ms 71968 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);
	if(n > 1) 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 65 ms 62968 KB Output is correct
2 Correct 56 ms 62968 KB Output is correct
3 Correct 57 ms 63020 KB Output is correct
4 Correct 56 ms 62968 KB Output is correct
5 Correct 57 ms 63036 KB Output is correct
6 Correct 57 ms 62920 KB Output is correct
7 Incorrect 56 ms 62968 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 62968 KB Output is correct
2 Correct 56 ms 62968 KB Output is correct
3 Correct 57 ms 63020 KB Output is correct
4 Correct 56 ms 62968 KB Output is correct
5 Correct 57 ms 63036 KB Output is correct
6 Correct 57 ms 62920 KB Output is correct
7 Incorrect 56 ms 62968 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 62968 KB Output is correct
2 Correct 56 ms 62968 KB Output is correct
3 Correct 57 ms 63020 KB Output is correct
4 Correct 56 ms 62968 KB Output is correct
5 Correct 57 ms 63036 KB Output is correct
6 Correct 57 ms 62920 KB Output is correct
7 Incorrect 56 ms 62968 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 68752 KB Output is correct
2 Incorrect 161 ms 71968 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 62968 KB Output is correct
2 Correct 56 ms 62968 KB Output is correct
3 Correct 57 ms 63020 KB Output is correct
4 Correct 56 ms 62968 KB Output is correct
5 Correct 57 ms 63036 KB Output is correct
6 Correct 57 ms 62920 KB Output is correct
7 Incorrect 56 ms 62968 KB Output isn't correct
8 Halted 0 ms 0 KB -