結果

問題 No.1295 木と駒
ユーザー 沙耶花沙耶花
提出日時 2020-05-21 09:46:22
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 900 ms / 2,000 ms
コード長 6,112 bytes
コンパイル時間 3,336 ms
コンパイル使用メモリ 245,784 KB
実行使用メモリ 79,084 KB
最終ジャッジ日時 2024-07-04 18:33:49
合計ジャッジ時間 27,236 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 1 ms
6,944 KB
testcase_09 AC 1 ms
6,944 KB
testcase_10 AC 1 ms
6,940 KB
testcase_11 AC 2 ms
6,944 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 2 ms
6,944 KB
testcase_14 AC 838 ms
42,856 KB
testcase_15 AC 831 ms
42,852 KB
testcase_16 AC 854 ms
42,856 KB
testcase_17 AC 856 ms
42,980 KB
testcase_18 AC 851 ms
42,844 KB
testcase_19 AC 466 ms
44,160 KB
testcase_20 AC 583 ms
79,084 KB
testcase_21 AC 488 ms
54,416 KB
testcase_22 AC 477 ms
44,908 KB
testcase_23 AC 407 ms
60,772 KB
testcase_24 AC 405 ms
60,892 KB
testcase_25 AC 344 ms
46,496 KB
testcase_26 AC 485 ms
78,952 KB
testcase_27 AC 529 ms
78,948 KB
testcase_28 AC 900 ms
74,600 KB
testcase_29 AC 532 ms
78,952 KB
testcase_30 AC 513 ms
79,080 KB
testcase_31 AC 528 ms
79,080 KB
testcase_32 AC 682 ms
67,472 KB
testcase_33 AC 725 ms
42,080 KB
testcase_34 AC 860 ms
44,256 KB
testcase_35 AC 705 ms
41,956 KB
testcase_36 AC 761 ms
43,228 KB
testcase_37 AC 749 ms
42,076 KB
testcase_38 AC 808 ms
43,100 KB
testcase_39 AC 767 ms
42,080 KB
testcase_40 AC 714 ms
41,952 KB
testcase_41 AC 394 ms
43,512 KB
testcase_42 AC 439 ms
44,156 KB
testcase_43 AC 424 ms
44,152 KB
testcase_44 AC 417 ms
44,044 KB
testcase_45 AC 427 ms
44,024 KB
testcase_46 AC 436 ms
44,028 KB
testcase_47 AC 419 ms
44,028 KB
testcase_48 AC 473 ms
44,028 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 | 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>
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;	
}
0