이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define ll int
#define f first
#define s second
#define pb push_back
using namespace std;
ll P[500002][20],lvl[500002],pp[500002],in[500002],out[500002],timer,ch[500002];
ll n,k,bst[500002],c[500002],par[500002],p[500002],sz[500002],raod[500002];
ll fix[500002];
set<ll>st[500002];
vector<ll>v[500002],del[500002],fer[500002];
void dfs(ll x,ll par) {
P[x][0]=par;
pp[x] = par;
for (int i=1;i<=19;i++)
P[x][i]=P[P[x][i-1]][i-1];
timer++;
in[x]=timer;
ch[x] = 1;
for (int i=0;i<v[x].size();i++)
if (v[x][i] != par) {
lvl[v[x][i]]=lvl[x]+1;
dfs(v[x][i],x);
ch[x] += ch[v[x][i]];
}
out[x]=timer;
}
ll lca(ll a,ll b) {
if(lvl[a] > lvl[b])swap(a,b);
if (in[a] <= in[b] && out[b] <= out[a]) return a;
for (int i=19;i>=0;i--)
if (P[a][i])
if (!(in[P[a][i]] <= in[b] && out[b] <= out[P[a][i]]))
a=P[a][i];
return P[a][0];
}
ll find(ll x){
if(p[x] == x)return x;
return p[x] = find(p[x]);
}
void join(ll x,ll y){
//cout << x << " " << y << endl;
x = find(x);
y = find(y);
if(x == y)return;
if(sz[y] > sz[x])swap(x , y);
sz[x] += sz[y];
p[y] = x;
}
void solve(ll x){
if(v[x].size() == 0){
bst[x] = x;
if(par[c[x]] != x)st[x].insert(c[x]);
return;
}
for(int i=0; i<v[x].size(); i++)
solve(v[x][i]);
bst[x] = bst[v[x][0]];
if(st[bst[x]].size() > 0){
join(c[x] , (*st[bst[x]].begin()));
}
st[bst[x]].insert(c[x]);
for(int i=1; i<v[x].size(); i++){
ll t = bst[v[x][i]];
for(set<ll>::iterator it = st[t].begin(); it != st[t].end(); it++){
join(c[x] , (*it));
st[bst[x]].insert((*it));
}
}
for(int i=0; i<del[x].size(); i++)
st[bst[x]].erase(st[bst[x]].find(del[x][i]));
}
int main(){
ios::sync_with_stdio(false);
cin >> n >> k;
for(int i=1; i<n; i++){
ll x,y;
cin >> x >> y;
v[x].pb(y);
v[y].pb(x);
}
for(int i=1; i<=n; i++){
cin >> c[i];
fer[c[i]].pb(i);
}
dfs(1 , 0);
for(int i=1; i<=k; i++){
par[i] = fer[i][0];
for(int j=1; j<fer[i].size(); j++)
par[i] = lca(par[i] , fer[i][j]);
del[par[i]].pb(i);/*
for(int j=0; j<fer[i].size(); j++){
ll x = fer[i][j];
while(1){
join(i , c[x]);
if(x == par[i])break;
x = pp[x];
}
}*/
}
for(int i=1; i<=n; i++){
sz[i] = 1;
p[i] = i;
v[i].clear();
}
for(int i=2; i<=n; i++)
v[pp[i]].pb(i);
for(int i=1; i<=n; i++)
for(int j=1; j<v[i].size(); j++)
if(ch[v[i][j]] > ch[v[i][0]])
swap(v[i][j] , v[i][0]);
solve(1);
for(int i=1; i<=n; i++){
for(int j=0; j<v[i].size(); j++){
ll x = v[i][j];
if(find(c[i]) != find(c[x])){
raod[find(c[i])]++;
raod[find(c[x])]++;
}
}
}
ll ans = 1;
for(int i=1; i<=k; i++){
if(!fix[find(i)]){
fix[find(i)] = 1;
if(raod[find(i)] == 1)ans++;
}
}
cout << ans / 2 << '\n';
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
mergers.cpp: In function 'void dfs(int, int)':
mergers.cpp:20:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<v[x].size();i++)
~^~~~~~~~~~~~
mergers.cpp: In function 'void solve(int)':
mergers.cpp:57:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<v[x].size(); i++)
~^~~~~~~~~~~~
mergers.cpp:64:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1; i<v[x].size(); i++){
~^~~~~~~~~~~~
mergers.cpp:71:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<del[x].size(); i++)
~^~~~~~~~~~~~~~
mergers.cpp: In function 'int main()':
mergers.cpp:94:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=1; j<fer[i].size(); j++)
~^~~~~~~~~~~~~~
mergers.cpp:117:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=1; j<v[i].size(); j++)
~^~~~~~~~~~~~
mergers.cpp:125:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<v[i].size(); j++){
~^~~~~~~~~~~~
# | 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... |