結果
問題 | No.1295 木と駒 |
ユーザー |
![]() |
提出日時 | 2020-05-20 23:47:48 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,173 ms / 2,000 ms |
コード長 | 6,636 bytes |
コンパイル時間 | 4,348 ms |
コンパイル使用メモリ | 233,640 KB |
最終ジャッジ日時 | 2025-01-10 13:29:43 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 48 |
コンパイルメッセージ
main.cpp:189:25: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’ 189 | int get_dis(int u,int v,auto &H,auto &S){ | ^~~~ main.cpp:189:33: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’ 189 | int get_dis(int u,int v,auto &H,auto &S){ | ^~~~ main.cpp:201:11: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’ 201 | void dfs0(auto &E,int now,int p,auto &H,auto &S1,auto &S2){ | ^~~~ main.cpp:201:33: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’ 201 | void dfs0(auto &E,int now,int p,auto &H,auto &S1,auto &S2){ | ^~~~ main.cpp:201:41: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’ 201 | void dfs0(auto &E,int now,int p,auto &H,auto &S1,auto &S2){ | ^~~~ main.cpp:201:50: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’ 201 | void dfs0(auto &E,int now,int p,auto &H,auto &S1,auto &S2){ | ^~~~ main.cpp:217:11: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’ 217 | void dfs1(auto &E,int now,int p,auto &H,auto &S0,auto &S1,auto &S2){ | ^~~~ main.cpp:217:33: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’ 217 | void dfs1(auto &E,int now,int p,auto &H,auto &S0,auto &S1,auto &S2){ | ^~~~ main.cpp:217:41: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’ 217 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define modulo 1000000007#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)#define Inf 1000000001struct 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,typename F>struct segtree{F func;vector<T> v;int n;T init_value;segtree(int sz,F f,T iv):func(f){init_value = iv;n=1;while(true){if(n>=sz)break;n*=2;}v.resize(2*n,init_value);for(int i=n-1;i>=0;i--){v[i]=func(v[i<<1],v[(i<<1)+1]);}}segtree(vector<T> &x,F f,T iv):func(f){init_value = iv;n=1;while(true){if(n>=x.size())break;n*=2;}v.resize(2*n,init_value);for(int i=0;i<x.size();i++){v[n+i]=x[i];}for(int i=n-1;i>=0;i--){v[i]=func(v[i<<1],v[(i<<1)+1]);}}void update(int x,T val){x+=n;v[x]=val;while(x>0){x>>=1;v[x]=func(v[x<<1],v[(x<<1)+1]);}}T query(int l,int r){if(l>=r)return init_value;l+=n;r+=n;T res1 = init_value;T res2 = init_value;while(true){if(l&1){res1=func(res1,v[l++]);}if(r&1){res2=func(v[--r],res2);}if(l>=r)break;l>>=1;r>>=1;}return func(res1,res2);}void show(){int n = 1;for(int i=1;i<v.size();i++){for(int j=0;j<n;j++){if(j!=0)cout<<' ';cout<<v[i+j];}cout<<endl;i+=n-1;n*=2;}}};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;};segtree<int,decltype(f)> S0(d0,f,0),S1(d1,f,0),S2(d2,f,0);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;}