結果

問題 No.1295 木と駒
ユーザー 沙耶花沙耶花
提出日時 2020-05-27 09:49:44
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 886 ms / 2,000 ms
コード長 6,976 bytes
コンパイル時間 3,560 ms
コンパイル使用メモリ 244,472 KB
実行使用メモリ 78,312 KB
最終ジャッジ日時 2024-07-04 18:35:29
合計ジャッジ時間 25,846 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 1 ms
5,376 KB
testcase_14 AC 756 ms
46,696 KB
testcase_15 AC 732 ms
46,668 KB
testcase_16 AC 745 ms
46,692 KB
testcase_17 AC 725 ms
46,696 KB
testcase_18 AC 747 ms
46,684 KB
testcase_19 AC 419 ms
47,864 KB
testcase_20 AC 567 ms
78,188 KB
testcase_21 AC 453 ms
56,848 KB
testcase_22 AC 428 ms
48,492 KB
testcase_23 AC 368 ms
62,048 KB
testcase_24 AC 365 ms
62,172 KB
testcase_25 AC 309 ms
50,336 KB
testcase_26 AC 458 ms
78,188 KB
testcase_27 AC 510 ms
78,184 KB
testcase_28 AC 886 ms
74,344 KB
testcase_29 AC 502 ms
78,184 KB
testcase_30 AC 488 ms
78,056 KB
testcase_31 AC 493 ms
78,312 KB
testcase_32 AC 651 ms
67,988 KB
testcase_33 AC 616 ms
45,920 KB
testcase_34 AC 796 ms
47,844 KB
testcase_35 AC 622 ms
45,792 KB
testcase_36 AC 689 ms
46,940 KB
testcase_37 AC 695 ms
45,792 KB
testcase_38 AC 711 ms
46,816 KB
testcase_39 AC 868 ms
45,664 KB
testcase_40 AC 794 ms
45,748 KB
testcase_41 AC 361 ms
47,488 KB
testcase_42 AC 403 ms
47,864 KB
testcase_43 AC 426 ms
47,744 KB
testcase_44 AC 408 ms
47,868 KB
testcase_45 AC 397 ms
47,868 KB
testcase_46 AC 402 ms
47,868 KB
testcase_47 AC 414 ms
47,740 KB
testcase_48 AC 442 ms
47,612 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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:216:11: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  216 | void dfs1(auto &E,int now,int p,auto &H,auto &S0,auto &S1,auto &S2){
      |           ^~~~
main.cpp:216:33: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  216 | void dfs1(auto &E,int now,int p,auto &H,auto &S0,auto &S1,auto &S2){
      |                                 ^~~~
main.cpp:216:41: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  216 | void dfs1(auto &E,int now,int p,auto &H,auto &S0,auto &S1,auto &S2){
      |

ソースコード

diff # 

#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,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);
			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);
	
	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(0,from,H,S0)>get_dis(0,to,H,S0))swap(from,to);
				int d = get_dis(0,to,H,S0);
				if(d>maxi){
					maxi = d;
					target = to;
				}
			}
		}
	}
	
	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;	
}
0