oj.uz

답안 #681441

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
681441 2023-01-13T05:45:00 Z flappybird Mergers (JOI19_mergers) C++17
0 / 100
 78 ms 41472 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 505050
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define fmax(a, b) (a) = (max((a), (b))
vector<int> adj[MAX];
int sp[MAX][MAXS];
int dep[MAX] = { 0, 1 };
vector<int> locs[MAX];
void dfs(int x, int p = 0) {
	sp[x][0] = p;
	int i;
	for (i = 1; i < MAXS; i++) sp[x][i] = sp[sp[x][i - 1]][i - 1];
	for (auto v : adj[x]) if (v != p) {
		dep[v] = dep[x] + 1;
		dfs(v, x);
	}
}
int lca(int u, int v) {
	int i;
	if (dep[u] != dep[v]) {
		if (dep[u] > dep[v]) swap(u, v);
		int d = dep[v] - dep[u];
		for (i = 0; i < MAXS; i++) if ((d >> i) & 1) v = sp[v][i];
	}
	if (u == v) return u;
	for (i = MAXS - 1; i >= 0; i--) if (sp[u][i] != sp[v][i]) u = sp[u][i], v = sp[v][i];
	return sp[u][0];
}
int p[MAX];
int psum[MAX];
int col[MAX];
int find(int x) {
	if (p[x] == x) return x;
	return p[x] = find(p[x]);
}
void uni(int u, int v) {
	u = find(u);
	v = find(v);
	if (adj[u].size() < adj[v].size()) swap(u, v);
	for (auto x : adj[v]) adj[u].push_back(v);
	p[v] = u;
}
void calc(int x, int p = 0) {
	for (auto v : adj[x]) if (v != p) {
		calc(v, x);
		psum[x] += psum[v];
	}
}
int nleaf(int x, int p = 0) {
	int cnt = 0;
	int sum = 0;
	for (auto v : adj[x]) {
		v = find(v);
		if (v == x) continue;
		cnt++;
		if (v == p) continue;
		sum += nleaf(v, x);
	}
	if (cnt == 1) sum++;
	return sum;
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, K;
	cin >> N >> K;
	int i;
	int a, b;
	for (i = 1; i < N; i++) {
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(1);
	for (i = 1; i <= N; i++) {
		cin >> col[i];
		locs[col[i]].push_back(i);
	}
	for (i = 1; i <= K; i++) {
		if (locs[i].size() > 1) {
			int j;
			for (j = 1; j < locs[i].size(); j++) {
				int l = lca(locs[i][j], locs[i][j - 1]);
				psum[locs[i][j]]++;
				psum[locs[i][j - 1]]++;
				psum[l] -= 2;
			}
		}
	}
	for (i = 1; i <= N; i++) p[i] = i;
	calc(1);
	for (i = 2; i <= N; i++) if (psum[i]) uni(i, sp[i][0]);
	cout << (nleaf(find(1)) + 1) / 2;
}

Compilation message

mergers.cpp: In function 'void uni(int, int)':
mergers.cpp:52:12: warning: unused variable 'x' [-Wunused-variable]
   52 |  for (auto x : adj[v]) adj[u].push_back(v);
      |            ^
mergers.cpp: In function 'int main()':
mergers.cpp:93:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |    for (j = 1; j < locs[i].size(); j++) {
      |                ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 24.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 38184 KB Output is correct
2 Correct 68 ms 41472 KB Output is correct
3 Incorrect 14 ms 24532 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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