이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long ;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l) == r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 500010, MAX_K = 20;
int n, k, belong[MAX_N];
vector<int> edge[MAX_N];
vector<int> state[MAX_N];
ll sum[MAX_N];
int anc[MAX_K][MAX_N], in[MAX_N], out[MAX_N];
bool isanc(int a, int b) { return in[a] <= in[b] && out[a] >= out[b]; }
void dfs(int x, int lst = 1) {
static int t;
anc[0][x] = lst;
in[x] = ++t;
for (int u : edge[x]) if (u != lst)
dfs(u, x);
out[x] = t;
}
void dfs2(int x, int lst = -1) {
for (int u : edge[x]) if (u != lst) {
dfs2(u, x);
sum[x] += sum[u];
}
}
vector<int> vir;
void dfs3(int x, int lst = -1) {
for (int u : edge[x]) if (u != lst)
dfs3(u, x);
int son = 0;
for (int u : edge[x]) if (u != lst)
if (sum[u] == 0) ++son;
if (sum[x] == 0 && lst != -1) ++son;
if (son) vir.pb(x);
}
int getlca(int a, int b) {
for (int d = MAX_K-1;d >= 0;--d)
if (!isanc(anc[d][a], b))
a = anc[d][a];
return isanc(a, b) ? a : anc[0][a];
}
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> k;
for (int a, b, i = 1;i < n;++i) {
cin >> a >> b;
edge[a].pb(b), edge[b].pb(a);
}
for (int i = 1;i <= n;++i) {
cin >> belong[i];
state[ belong[i] ].pb(i);
}
int rt = 1;
while (edge[rt].size() > 1) ++rt;
if (k == 1) return cout << 0 << '\n', 0;
dfs(rt);
for (int d = 1;d < MAX_K;++d)
for (int i = 1;i <= n;++i)
anc[d][i] = anc[d-1][ anc[d-1][i] ];
for (int i = 1;i <= k;++i) {
if (state[i].size() > 1) {
sort(AI(state[i]), [&](int a, int b) {
return in[a] < in[b];
});
for (int x : state[i])
++sum[x];
sum[ getlca(state[i][0], state[i].back()) ] -= state[i].size();
}
}
dfs2(rt);
dfs3(rt);
sort(AI(vir), [&](int a, int b) {
return in[a] < in[b]; });
debug(AI(vir));
vector<int> all;
for (int i = 0;i < vir.size();++i) {
all.pb(vir[i]);
if (i+1 < vir.size())
all.pb(getlca(vir[i], vir[i+1]));
}
sort(AI(all), [&](int a, int b) {
return in[a] < in[b]; });
all.erase(unique(AI(all)), end(all));
debug(AI(all));
vector<int> stk;
vector<int> cnt(n + 10);
for (int u : all) {
while (stk.size()) {
int x = stk.back();
DE(x, u);
if (isanc(x, u)) break;
stk.pop_back();
}
if (stk.size()) {
int x = stk.back();
DE(x, u);
++cnt[x], ++cnt[u];
}
stk.pb(u);
}
int res = 0;
for (int u : all)
res += cnt[u] == 1;
res = (res+1) / 2;
cout << res << '\n';
}
컴파일 시 표준 에러 (stderr) 메시지
mergers.cpp: In function 'int32_t main()':
mergers.cpp:15:20: warning: statement has no effect [-Wunused-value]
15 | #define debug(...) 0
| ^
mergers.cpp:103:2: note: in expansion of macro 'debug'
103 | debug(AI(vir));
| ^~~~~
mergers.cpp:106:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | for (int i = 0;i < vir.size();++i) {
| ~~^~~~~~~~~~~~
mergers.cpp:108:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | if (i+1 < vir.size())
| ~~~~^~~~~~~~~~~~
mergers.cpp:15:20: warning: statement has no effect [-Wunused-value]
15 | #define debug(...) 0
| ^
mergers.cpp:117:2: note: in expansion of macro 'debug'
117 | debug(AI(all));
| ^~~~~
mergers.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
mergers.cpp:128:4: note: in expansion of macro 'DE'
128 | DE(x, u);
| ^~
mergers.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
mergers.cpp:134:4: note: in expansion of macro 'DE'
134 | DE(x, u);
| ^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |