HITACHI2020 C. ThREE
Difficulty:2013
問題文
#HITACH #HIT
#木 #貪欲
問題
解法
実装
提出コード
code:cpp
bool solve(){
LL(n);
vector<vector<ll>>g(n);
rep(i,n-1){
LL(a,b);a--,b--;
ga.push_back(b);
gb.push_back(a);
}
vector<ll>dist(n,INF);
queue<ll>q;
q.push(0);
dist0 = 0;
while(q.size()){
ll pos = q.front();q.pop();
for(auto to:gpos){
if(chmin(distto,distpos+1)){
q.push(to);
}
}
}
vector<vector<ll>>vec(2);
rep(i,n){
vec[disti%2].push_back(i);
}
vector<ll>ans(n,-1);
vector<vector<ll>>cnt(3);
rep(i,1,n+1){
cnti%3.push_back(i);
}
if(vec1.size()<=n/3){
swap(vec1,vec0);
}
if(vec0.size()<=n/3){
for(auto i:vec0){
ansi = cnt0.back();
cnt0.pop_back();
}
ll i{};
while(cnt0.size()&&i<vec1.size()){
ans[vec1i++] = cnt0.back();
cnt0.pop_back();
}
while(cnt1.size()&&i<vec1.size()){
ans[vec1i++] = cnt1.back();
cnt1.pop_back();
}
while(cnt2.size()&&i<vec1.size()){
ans[vec1i++] = cnt2.back();
cnt2.pop_back();
}
}
else{
ll l{},r{};
while(cnt1.size()&&l<vec1.size()){
ans[vec1l++] = cnt1.back();
cnt1.pop_back();
}
while(cnt0.size()&&l<vec1.size()){
ans[vec1l++] = cnt0.back();
cnt0.pop_back();
}
while(cnt2.size()&&r<vec0.size()){
ans[vec0r++] = cnt2.back();
cnt2.pop_back();
}
while(cnt0.size()&&r<vec0.size()){
ans[vec0r++] = cnt0.back();
cnt0.pop_back();
}
}
O(ans);
return false;
}