#997830 (C++17) No.2822 Lights Up! (Tree Edition)

提出ソース

結果

問題	No.2822 Lights Up! (Tree Edition)
ユーザー	kmjp
提出日時	2024-07-26 22:38:19
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	64 ms / 2,000 ms
コード長	2,129 bytes
コンパイル時間	2,588 ms
コンパイル使用メモリ	214,648 KB
実行使用メモリ	24,116 KB
最終ジャッジ日時	2024-07-26 22:38:28
合計ジャッジ時間	8,540 ms
ジャッジサーバーID （参考情報）	judge5 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	8 ms 10,624 KB
testcase_01	AC	7 ms 10,624 KB
testcase_02	AC	58 ms 23,492 KB
testcase_03	AC	62 ms 23,552 KB
testcase_04	AC	57 ms 22,912 KB
testcase_05	AC	64 ms 23,552 KB
testcase_06	AC	58 ms 24,116 KB
testcase_07	AC	63 ms 23,648 KB
testcase_08	AC	37 ms 14,848 KB
testcase_09	AC	52 ms 22,528 KB
testcase_10	AC	54 ms 19,712 KB
testcase_11	AC	35 ms 18,048 KB
testcase_12	AC	40 ms 15,872 KB
testcase_13	AC	47 ms 15,360 KB
testcase_14	AC	62 ms 19,712 KB
testcase_15	AC	43 ms 17,024 KB
testcase_16	AC	9 ms 10,880 KB
testcase_17	AC	9 ms 11,136 KB
testcase_18	AC	13 ms 11,520 KB
testcase_19	AC	9 ms 11,648 KB
testcase_20	AC	9 ms 11,008 KB
testcase_21	AC	13 ms 11,904 KB
testcase_22	AC	11 ms 12,032 KB
testcase_23	AC	11 ms 11,648 KB
testcase_24	AC	10 ms 11,776 KB
testcase_25	AC	9 ms 11,136 KB
testcase_26	AC	11 ms 11,648 KB
testcase_27	AC	8 ms 10,752 KB
testcase_28	AC	12 ms 11,776 KB
testcase_29	AC	16 ms 12,288 KB
testcase_30	AC	13 ms 11,648 KB
testcase_31	AC	9 ms 11,136 KB
testcase_32	AC	13 ms 12,032 KB
testcase_33	AC	13 ms 12,032 KB
testcase_34	AC	13 ms 12,160 KB
testcase_35	AC	12 ms 12,160 KB
testcase_36	AC	14 ms 12,032 KB
testcase_37	AC	12 ms 12,160 KB
testcase_38	AC	12 ms 12,032 KB
testcase_39	AC	13 ms 12,160 KB
testcase_40	AC	13 ms 12,032 KB
testcase_41	AC	12 ms 12,160 KB
testcase_42	AC	13 ms 12,032 KB
testcase_43	AC	12 ms 12,032 KB
testcase_44	AC	13 ms 11,904 KB
testcase_45	AC	13 ms 12,032 KB
testcase_46	AC	12 ms 12,032 KB
testcase_47	AC	16 ms 12,288 KB
testcase_48	AC	8 ms 10,752 KB
testcase_49	AC	8 ms 10,880 KB
testcase_50	AC	8 ms 10,880 KB
testcase_51	AC	8 ms 10,880 KB
testcase_52	AC	8 ms 10,880 KB
testcase_53	AC	8 ms 10,880 KB
testcase_54	AC	8 ms 11,008 KB
testcase_55	AC	8 ms 10,880 KB
testcase_56	AC	7 ms 11,008 KB
testcase_57	AC	8 ms 11,008 KB
testcase_58	AC	8 ms 11,008 KB
testcase_59	AC	8 ms 10,880 KB
testcase_60	AC	8 ms 10,752 KB
testcase_61	AC	9 ms 11,008 KB
testcase_62	AC	8 ms 10,880 KB
testcase_63	AC	8 ms 10,880 KB
testcase_64	AC	8 ms 10,880 KB
testcase_65	AC	8 ms 10,880 KB
testcase_66	AC	8 ms 10,880 KB
testcase_67	AC	8 ms 10,880 KB
testcase_68	AC	8 ms 10,880 KB
testcase_69	AC	7 ms 10,880 KB
testcase_70	AC	8 ms 10,752 KB
testcase_71	AC	8 ms 11,008 KB
testcase_72	AC	8 ms 10,880 KB
testcase_73	AC	8 ms 10,880 KB
testcase_74	AC	8 ms 10,880 KB
testcase_75	AC	8 ms 10,880 KB
testcase_76	AC	11 ms 10,880 KB
testcase_77	AC	10 ms 10,880 KB
testcase_78	AC	8 ms 11,008 KB
testcase_79	AC	8 ms 11,008 KB
testcase_80	AC	8 ms 10,752 KB
testcase_81	AC	7 ms 10,752 KB
testcase_82	AC	8 ms 10,880 KB
testcase_83	AC	7 ms 10,752 KB
testcase_84	AC	8 ms 10,624 KB
testcase_85	AC	8 ms 10,752 KB
testcase_86	AC	7 ms 10,752 KB
testcase_87	AC	8 ms 10,752 KB
testcase_88	AC	8 ms 10,752 KB
testcase_89	AC	8 ms 10,880 KB
testcase_90	AC	8 ms 10,752 KB
testcase_91	AC	8 ms 10,752 KB
testcase_92	AC	7 ms 10,752 KB
testcase_93	AC	7 ms 10,752 KB
testcase_94	AC	8 ms 10,752 KB
testcase_95	AC	7 ms 10,880 KB
testcase_96	AC	8 ms 10,624 KB
testcase_97	AC	8 ms 10,752 KB
testcase_98	AC	8 ms 10,752 KB
testcase_99	AC	8 ms 10,752 KB
testcase_100	AC	7 ms 10,752 KB
testcase_101	AC	8 ms 10,752 KB
testcase_102	AC	8 ms 10,752 KB
testcase_103	AC	8 ms 10,752 KB
testcase_104	AC	8 ms 10,752 KB
testcase_105	AC	8 ms 10,880 KB
testcase_106	AC	8 ms 10,752 KB
testcase_107	AC	8 ms 10,752 KB
testcase_108	AC	8 ms 10,752 KB
testcase_109	AC	8 ms 10,880 KB
testcase_110	AC	8 ms 10,880 KB
testcase_111	AC	7 ms 10,624 KB
testcase_112	AC	8 ms 10,752 KB
testcase_113	AC	8 ms 10,752 KB
testcase_114	AC	8 ms 10,624 KB
testcase_115	AC	8 ms 10,752 KB
testcase_116	AC	8 ms 10,624 KB
testcase_117	AC	8 ms 10,624 KB
testcase_118	AC	8 ms 10,752 KB
testcase_119	AC	8 ms 10,752 KB
testcase_120	AC	8 ms 10,752 KB
testcase_121	AC	8 ms 10,624 KB
testcase_122	AC	8 ms 10,752 KB
testcase_123	AC	8 ms 10,752 KB
testcase_124	AC	8 ms 10,752 KB
testcase_125	AC	8 ms 10,752 KB
testcase_126	AC	7 ms 10,752 KB
testcase_127	AC	10 ms 10,752 KB
testcase_128	AC	8 ms 10,752 KB
testcase_129	AC	8 ms 10,752 KB
testcase_130	AC	8 ms 10,752 KB
testcase_131	AC	8 ms 10,752 KB
testcase_132	AC	7 ms 10,752 KB
testcase_133	AC	8 ms 10,752 KB
testcase_134	AC	7 ms 10,752 KB
testcase_135	AC	7 ms 10,624 KB
testcase_136	AC	7 ms 10,880 KB
testcase_137	AC	7 ms 10,752 KB
testcase_138	AC	8 ms 10,752 KB
testcase_139	AC	8 ms 10,880 KB
testcase_140	AC	8 ms 10,880 KB
testcase_141	AC	8 ms 10,752 KB
testcase_142	AC	8 ms 10,752 KB
testcase_143	AC	8 ms 10,752 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define FORR2(x,y,arr) for(auto& [x,y]:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
template<class T> bool chmax(T &a, const T &b) { if(a<b){a=b;return 1;}return 0;}
template<class T> bool chmin(T &a, const T &b) { if(a>b){a=b;return 1;}return 0;}
//-------------------------------------------------------

int N;
vector<int> E[202020];
string S;

int P[21][200005],D[200005];
int L[202020],R[202020],re[202020];
int id;
int C[101010];
int dif[101010];

vector<int> tar[101010];
int K;

void dfs(int cur) {
	FORR(e,E[cur]) if(e!=P[0][cur]) D[e]=D[cur]+1, P[0][e]=cur, dfs(e);
	L[cur]=id++;
	re[L[cur]]=cur;
	R[cur]=id;
}

int lca(int a,int b) {
	int ret=0,i,aa=a,bb=b;
	if(D[aa]>D[bb]) swap(aa,bb);
	for(i=19;i>=0;i--) if(D[bb]-D[aa]>=1<<i) bb=P[i][bb];
	for(i=19;i>=0;i--) if(P[i][aa]!=P[i][bb]) aa=P[i][aa], bb=P[i][bb];
	return (aa==bb)?aa:P[0][aa];               // vertex
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	for(i=1;i<N;i++) {
		cin>>x;
		P[0][i]=x-1;
		E[x-1].push_back(i);
	}
	cin>>S;
	dfs(0);
	FOR(i,19) FOR(x,N) P[i+1][x]=P[i][P[i][x]];
	for(i=1;i<N;i++) C[i]=S[i-1]=='#';
	
	cin>>K;
	FOR(i,K) {
		cin>>x>>y;
		x--,y--;
		if(L[x]>L[y]) swap(x,y);
		tar[x].push_back(y);
	}
	FOR(i,N-1) {
		x=re[i];
		vector<pair<int,int>> T;
		FORR(e,tar[x]) T.push_back({L[e],e});
		sort(ALL(T));
		T.erase(unique(ALL(T)),T.end());
		
		if(T.size()>1) {
			FOR(j,T.size()-1) {
				tar[T[j].second].push_back(T[j+1].second);
			}
		}
		if(dif[x]!=C[x]) {
			if(T.empty()) {
				cout<<"No"<<endl;
				return;
			}
			y=T[0].second;
			dif[x]^=1;
			dif[y]^=1;
		}
		dif[P[0][x]]^=dif[x];
		
	}
	cout<<"Yes"<<endl;
	
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}

yukicoder

結果

テストケース

ソースコード