oj.uz

Submission #133231

# Submission time Handle Problem Language Result Execution time Memory
133231 2019-07-20T09:41:31 Z ekrem Mergers (JOI19_mergers) C++
0 / 100
 224 ms 113248 KB 
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)/2)
#define coc g[node][i]
#define LOGN 20
#define mod 1000000007
#define inf 1000000009
#define N 1000005
using namespace std;

typedef long long ll;
typedef pair < int , int > ii;

int n, k, ans, l[N], a[N], der[N], par[LOGN + 5][N];
vector < int > g[N], cik[N];
set < int > s[N];
set < int > :: iterator it;

void hazirla(int node, int pr, int dr){
	der[node] = dr;
	par[0][node] = pr;
	for(int i = 0; i < g[node].size(); i++)
		if(coc != pr)
			hazirla(coc, node, dr + 1);
}

int lca(int u, int v){
	if(!u or !v)
		return u + v;
	if(der[u] < der[v])
		swap(u, v);
	for(int i = LOGN; i >= 0; i--)
		if(der[par[i][u]] >= der[v])
			u = par[i][u];
	if(u == v)
		return u;
	for(int i = LOGN; i >= 0; i--)
		if(par[i][u] != par[i][v]){
			u = par[i][u];
			v = par[i][v];
		}
	return par[0][u];
}

bool dfs(int node, int par){
	bool don = 0;
	for(int i = 0; i < g[node].size(); i++)
		if(coc != par){
			don |= dfs(coc, node);
			if(s[coc].size() > s[node].size())
				swap(s[node], s[coc]);
			for(it = s[coc].begin(); it != s[coc].end(); it++)
				s[node].insert(*it);
		}
	// cout << node << " " << don << endl;
	s[node].insert(a[node]);
	for(int i = 0; i < cik[node].size(); i++)
		s[node].erase(cik[node][i]);
	if(!don and s[node].empty() and par){
		// cout << node << endl;
		don = 1;
		ans++;
	}
	return don;
}

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%d %d",&n ,&k);
	for(int i = 1; i < n; i++){
		int u, v;
		scanf("%d %d",&u ,&v);
		g[v].pb(u);
		g[u].pb(v);
	}
	hazirla(1, 0, 1);
	for(int i = 1; i <= LOGN; i++)
		for(int j = 1; j <= n; j++)
			par[i][j] = par[i - 1][par[i - 1][j]];
	
	for(int i = 1; i <= n; i++){
		scanf("%d",a + i);
		l[a[i]] = lca(l[a[i]], i);
	}
	for(int i = 1; i <= k; i++)
		cik[l[i]].pb(i);
	dfs(1, 0);
	if(!ans)
		printf("0\n");
	else
		printf("%d",max(1, ans - 1));
	// cout << ans << endl;
	return 0;
}

Compilation message

mergers.cpp: In function 'void hazirla(int, int, int)':
mergers.cpp:27:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[node].size(); i++)
                 ~~^~~~~~~~~~~~~~~~
mergers.cpp: In function 'bool dfs(int, int)':
mergers.cpp:52:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[node].size(); i++)
                 ~~^~~~~~~~~~~~~~~~
mergers.cpp:62:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < cik[node].size(); i++)
                 ~~^~~~~~~~~~~~~~~~~~
mergers.cpp: In function 'int main()':
mergers.cpp:75: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:78: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:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",a + i);
   ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 94456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 94456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 94456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 113248 KB Output is correct
2 Incorrect 209 ms 112312 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 94456 KB Output isn't correct
2 Halted 0 ms 0 KB -