結果
| 問題 |
No.1295 木と駒
|
| コンテスト | |
| ユーザー |
 沙耶花
|
| 提出日時 | 2020-05-21 09:46:22 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,345 ms / 2,000 ms |
| コード長 | 6,112 bytes |
| コンパイル時間 | 4,191 ms |
| コンパイル使用メモリ | 237,200 KB |
| 最終ジャッジ日時 | 2025-01-10 13:34:10 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 48 |
コンパイルメッセージ
main.cpp:160:25: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
160 | int get_dis(int u,int v,auto &H,auto &S){
| ^~~~
main.cpp:160:33: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
160 | int get_dis(int u,int v,auto &H,auto &S){
| ^~~~
main.cpp:172:11: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
172 | void dfs0(auto &E,int now,int p,auto &H,auto &S1,auto &S2){
| ^~~~
main.cpp:172:33: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
172 | void dfs0(auto &E,int now,int p,auto &H,auto &S1,auto &S2){
| ^~~~
main.cpp:172:41: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
172 | void dfs0(auto &E,int now,int p,auto &H,auto &S1,auto &S2){
| ^~~~
main.cpp:172:50: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
172 | void dfs0(auto &E,int now,int p,auto &H,auto &S1,auto &S2){
| ^~~~
main.cpp:188:11: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
188 | void dfs1(auto &E,int now,int p,auto &H,auto &S0,auto &S1,auto &S2){
| ^~~~
main.cpp:188:33: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
188 | void dfs1(auto &E,int now,int p,auto &H,auto &S0,auto &S1,auto &S2){
| ^~~~
main.cpp:188:41: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
188 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000001
struct HLD{
vector<int> sz,parent,depth,root,pos;
vector<int> arr;
HLD(vector<vector<int>> &E){
sz.resize(E.size(),1);
parent.resize(E.size(),0);
depth.resize(E.size(),0);
root.resize(E.size(),0);
pos.resize(E.size(),0);
dfs(0,-1,E);
dfs2(0,-1,E,0);
}
void dfs(int now,int p,vector<vector<int>> &E){
parent[now] = p;
if(p==-1){
depth[now] = 0;
}
else{
depth[now] = depth[p]+1;
}
for(int i=0;i<E[now].size();i++){
int to = E[now][i];
if(to==p)continue;
dfs(to,now,E);
sz[now] += sz[to];
}
}
void dfs2(int now,int p,vector<vector<int>> &E,int r){
pos[now] = arr.size();
arr.push_back(now);
root[now] = r;
int maxi = 0;
int ind = -1;
for(int i=0;i<E[now].size();i++){
int to = E[now][i];
if(to==p)continue;
if(maxi<sz[to]){
maxi = sz[to];
ind = to;
}
}
if(ind==-1)return;
dfs2(ind,now,E,r);
for(int i=0;i<E[now].size();i++){
int to = E[now][i];
if(to==p||to==ind)continue;
dfs2(to,now,E,to);
}
}
vector<pair<int,int>> query(int u,int v){
vector<pair<int,int>> ret;
int t = 0;
while(root[u]!=root[v]){
if(depth[root[u]] <= depth[root[v]]){
ret.insert(ret.begin()+t,{pos[root[v]], pos[v]});
v = parent[root[v]];
}
else{
ret.insert(ret.begin()+t,{pos[u],pos[root[u]]});
u = parent[root[u]];
t++;
}
}
ret.insert(ret.begin()+t,{pos[u],pos[v]});
return ret;
}
};
template <typename T>
struct BIT{
vector<T> v;
int n;
const T init_value = 0;
BIT(int sz){
n=sz+1;
v.resize(n,init_value);
}
BIT(vector<T> &x){
n=x.size()+1;
v.resize(n,init_value);
for(int i=0;i<x.size();i++){
update(i,x[i]);
}
}
void update(int x,T val){
val = val - query(x,x+1);
x++;
while(x < n){
v[x] = func(v[x],val);
x += x & (-x);
}
}
//区間[0,r)におけるクエリ処理
T query(int r){
T ret = init_value;
while(r>0){
ret = func(v[r],ret);
r -= r & (-r);
}
return ret;
}
T query(int l,int r){
return query(r) - query(l);
}
T func(T a,T b){
return a+b;
}
};
int N;
vector<vector<int>> E;
int cnt = 0;
int target = -1;
map<pair<int,int>,int> mp;
vector<bool> ans;
vector<vector<int>> get_fixedE(vector<vector<int>> E){
vector<vector<int>> ret(2*N-1,vector<int>());
int t = N;
for(int i=0;i<N;i++){
for(int j=0;j<E[i].size();j++){
int to = E[i][j];
if(i>to)continue;
mp[{i,to}]=t;
mp[{to,i}]=t;
ret[i].push_back(t);
ret[t].push_back(i);
ret[to].push_back(t);
ret[t].push_back(to);
t++;
}
}
return ret;
}
int get_dis(int u,int v,auto &H,auto &S){
auto V = H.query(u,v);
int ret = 0;
for(auto a:V){
int l = a.first;
int r = a.second;
if(l>r)swap(l,r);
ret += S.query(l,r+1);
}
return ret;
}
void dfs0(auto &E,int now,int p,auto &H,auto &S1,auto &S2){
for(int i=0;i<E[now].size();i++){
int to = E[now][i];
if(to==p)continue;
if(E[to][0]!=now){
S1.update(H.pos[mp[{now,to}]],1);
target = to;
cnt++;
}
if(E[now][0]==to||i+1==E[now].size()||(i+2==E[now].size()&&E[now].back()==p)){
S2.update(H.pos[mp[{now,to}]],1);
}
dfs0(E,to,now,H,S1,S2);
}
}
void dfs1(auto &E,int now,int p,auto &H,auto &S0,auto &S1,auto &S2){
bool F = false;
if(target == now){
F=true;
target = -1;
int maxi = -1;
for(int i=0;i<N;i++){
for(int j=0;j<E[i].size();j++){
int from = i;
int to = E[i][j];
int ind = H.pos[mp[{from,to}]];
if(S1.query(ind,ind+1)==1){
if(get_dis(now,from,H,S0)>get_dis(now,to,H,S0))swap(from,to);
int d = get_dis(now,to,H,S0);
if(d>maxi){
maxi = d;
target = to;
}
}
}
}
}
if(target==-1){
ans[now] = true;
}
else{
int d1 = get_dis(now,target,H,S0);
int d2 = get_dis(now,target,H,S1);
int d3 = get_dis(now,target,H,S2);
if(d2==cnt&&d1==d3){
ans[now]=true;
}
}
vector<int> Temp;
for(int i=0;i<E[now].size();i++){
int to = E[now][i];
int n = mp[{now,to}];
int fn = H.pos[n];
Temp.push_back(S2.query(fn,fn+1));
if(i==0||i+1==E[now].size())S2.update(fn,1);
else S2.update(fn,0);
}
for(int i=0;i<E[now].size();i++){
int to = E[now][i];
if(to==p)continue;
bool FF = false;
int n = mp[{now,to}];
int fn = H.pos[n];
if(S1.query(fn,fn+1)==1)cnt--;
S1.update(fn,0);
if(E[now][0]!=to){
cnt++;
S1.update(fn,1);
if(target==-1){
FF = true;
target = now;
}
}
vector<int> temp;
for(int j=0;j<E[to].size();j++){
int x = H.pos[mp[{to,E[to][j]}]];
temp.push_back(S2.query(x,x+1));
S2.update(x,0);
if(j==0||j+1==E[to].size())S2.update(x,1);
}
if(i+1==E[now].size()&&E[now].size()>=2){
int x = E[now][i-1];
int nn = mp[{now,x}];
int fnn = H.pos[nn];
S2.update(fnn,1);
}
dfs1(E,to,now,H,S0,S1,S2);
if(FF){
target = -1;
}
if(S1.query(fn,fn+1)==1)cnt--;
S1.update(fn,0);
if(E[to][0]!=now){
cnt++;
S1.update(fn,1);
}
for(int j=0;j<E[to].size();j++){
int x = H.pos[mp[{to,E[to][j]}]];
S2.update(x,temp[j]);
}
}
for(int i=0;i<E[now].size();i++){
int to = E[now][i];
int n = mp[{now,to}];
int fn = H.pos[n];
S2.update(fn,Temp[i]);
}
if(F)target = now;
}
int main(){
scanf("%d",&N);
E.resize(N,vector<int>());
for(int i=0;i<N-1;i++){
int u,v;
scanf("%d %d",&u,&v);
u--;v--;
E[u].push_back(v);
E[v].push_back(u);
}
for(int i=0;i<N;i++)sort(E[i].begin(),E[i].end());
vector<vector<int>> fixedE = get_fixedE(E);
HLD H(fixedE);
vector<int> d0(2*N-1,0);
vector<int> d1 = d0,d2 = d0;
for(int i=N;i<2*N-1;i++)d0[i] = 1;
{
vector<int> temp(2*N-1);
for(int i=0;i<2*N-1;i++){
temp[i] = d0[H.arr[i]];
}
d0 = temp;
}
auto f = [](int a,int b){
return a+b;
};
BIT<int> S0(d0),S1(d1),S2(d2);
dfs0(E,0,-1,H,S1,S2);
ans.resize(N,false);
dfs1(E,0,-1,H,S0,S1,S2);
for(int i=0;i<N;i++){
if(ans[i])printf("Yes\n");
else printf("No\n");
}
return 0;
}