oj.uz

답안 #133912

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
133912 2019-07-21T18:05:07 Z ekrem Mergers (JOI19_mergers) C++
0 / 100
 252 ms 111984 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, root, ans, deg[N], l[N], a[N], der[N], par[LOGN + 5][N];
vector < int > g[N], cik[N];
int amk, of, fl;
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];
}
 
int dfs(int node, int par){
	int 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);
		}
	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 and (fl or !amk) ){
		amk = node;
		of = par;
		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);
	}
	for(int i = 1; i <= n; i++)
		scanf("%d",a + i);

	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++){
		l[a[i]] = lca(l[a[i]], i);
	}
	for(int i = 1; i <= k; i++)
		cik[l[i]].pb(i);
	dfs(1, 0);


	for(int i = 1; i <= n; i++){
		l[i] = 0;
		cik[i].clear();
		s[i].clear();
	}

	fl = 1;
	ans = 0;
	// cout << amk << " " << of << endl;

	hazirla(amk, 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++){
		l[a[i]] = lca(l[a[i]], i);
	}
	for(int i = 1; i <= k; i++)
		cik[l[i]].pb(i);

	dfs(amk, 0);

	printf("%d",ans);
	return 0;
}

Compilation message

mergers.cpp: In function 'void hazirla(int, int, int)':
mergers.cpp:28:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[node].size(); i++)
                 ~~^~~~~~~~~~~~~~~~
mergers.cpp: In function 'int dfs(int, int)':
mergers.cpp:53: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:77: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:80: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:85: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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 87 ms 94460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 87 ms 94460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 87 ms 94460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 237 ms 111984 KB Output is correct
2 Incorrect 252 ms 110580 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 87 ms 94460 KB Output isn't correct
2 Halted 0 ms 0 KB -