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

提出ソース

結果

問題	No.2822 Lights Up! (Tree Edition)
ユーザー	kmjp
提出日時	2024-07-26 22:33:54
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	2,164 bytes
コンパイル時間	2,580 ms
コンパイル使用メモリ	214,616 KB
実行使用メモリ	34,224 KB
最終ジャッジ日時	2024-07-26 22:34:02
合計ジャッジ時間	8,226 ms
ジャッジサーバーID （参考情報）	judge5 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	8 ms 20,764 KB
testcase_01	AC	9 ms 22,688 KB
testcase_02	AC	56 ms 29,484 KB
testcase_03	WA	-
testcase_04	AC	54 ms 29,552 KB
testcase_05	AC	58 ms 29,500 KB
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	AC	53 ms 28,848 KB
testcase_10	WA	-
testcase_11	WA	-
testcase_12	AC	40 ms 26,004 KB
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	AC	9 ms 21,008 KB
testcase_18	WA	-
testcase_19	AC	9 ms 21,216 KB
testcase_20	AC	10 ms 23,124 KB
testcase_21	WA	-
testcase_22	AC	12 ms 23,376 KB
testcase_23	AC	12 ms 23,252 KB
testcase_24	AC	11 ms 23,332 KB
testcase_25	WA	-
testcase_26	AC	11 ms 23,328 KB
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	AC	10 ms 22,984 KB
testcase_32	AC	12 ms 23,556 KB
testcase_33	AC	12 ms 23,416 KB
testcase_34	WA	-
testcase_35	AC	12 ms 21,588 KB
testcase_36	WA	-
testcase_37	AC	12 ms 21,460 KB
testcase_38	AC	13 ms 23,508 KB
testcase_39	WA	-
testcase_40	WA	-
testcase_41	AC	12 ms 21,756 KB
testcase_42	AC	12 ms 21,720 KB
testcase_43	AC	12 ms 23,424 KB
testcase_44	AC	12 ms 23,556 KB
testcase_45	AC	13 ms 23,556 KB
testcase_46	AC	12 ms 21,588 KB
testcase_47	WA	-
testcase_48	WA	-
testcase_49	WA	-
testcase_50	WA	-
testcase_51	AC	8 ms 20,668 KB
testcase_52	AC	9 ms 22,856 KB
testcase_53	WA	-
testcase_54	AC	8 ms 20,780 KB
testcase_55	WA	-
testcase_56	AC	10 ms 22,952 KB
testcase_57	AC	9 ms 22,852 KB
testcase_58	AC	8 ms 20,804 KB
testcase_59	AC	8 ms 20,924 KB
testcase_60	AC	9 ms 22,828 KB
testcase_61	WA	-
testcase_62	WA	-
testcase_63	AC	8 ms 20,912 KB
testcase_64	AC	9 ms 22,852 KB
testcase_65	AC	9 ms 22,848 KB
testcase_66	WA	-
testcase_67	WA	-
testcase_68	WA	-
testcase_69	WA	-
testcase_70	WA	-
testcase_71	AC	8 ms 20,924 KB
testcase_72	WA	-
testcase_73	WA	-
testcase_74	AC	10 ms 22,852 KB
testcase_75	AC	7 ms 20,924 KB
testcase_76	WA	-
testcase_77	WA	-
testcase_78	WA	-
testcase_79	AC	7 ms 20,808 KB
testcase_80	AC	8 ms 22,820 KB
testcase_81	WA	-
testcase_82	AC	8 ms 22,956 KB
testcase_83	WA	-
testcase_84	AC	8 ms 22,700 KB
testcase_85	AC	8 ms 22,824 KB
testcase_86	WA	-
testcase_87	WA	-
testcase_88	AC	7 ms 20,776 KB
testcase_89	AC	8 ms 22,808 KB
testcase_90	WA	-
testcase_91	WA	-
testcase_92	AC	9 ms 22,952 KB
testcase_93	WA	-
testcase_94	WA	-
testcase_95	AC	9 ms 22,824 KB
testcase_96	AC	7 ms 20,768 KB
testcase_97	AC	8 ms 22,828 KB
testcase_98	WA	-
testcase_99	AC	9 ms 22,952 KB
testcase_100	WA	-
testcase_101	WA	-
testcase_102	AC	8 ms 22,808 KB
testcase_103	AC	7 ms 20,648 KB
testcase_104	AC	7 ms 20,768 KB
testcase_105	WA	-
testcase_106	WA	-
testcase_107	WA	-
testcase_108	WA	-
testcase_109	WA	-
testcase_110	WA	-
testcase_111	WA	-
testcase_112	AC	8 ms 20,772 KB
testcase_113	AC	8 ms 22,828 KB
testcase_114	WA	-
testcase_115	WA	-
testcase_116	AC	7 ms 20,764 KB
testcase_117	AC	9 ms 22,952 KB
testcase_118	AC	9 ms 22,696 KB
testcase_119	AC	9 ms 22,936 KB
testcase_120	AC	9 ms 22,820 KB
testcase_121	WA	-
testcase_122	WA	-
testcase_123	AC	7 ms 20,780 KB
testcase_124	WA	-
testcase_125	WA	-
testcase_126	AC	8 ms 20,776 KB
testcase_127	WA	-
testcase_128	AC	8 ms 20,772 KB
testcase_129	WA	-
testcase_130	WA	-
testcase_131	AC	8 ms 20,640 KB
testcase_132	WA	-
testcase_133	AC	9 ms 22,828 KB
testcase_134	AC	8 ms 22,824 KB
testcase_135	WA	-
testcase_136	AC	7 ms 20,888 KB
testcase_137	WA	-
testcase_138	AC	7 ms 20,632 KB
testcase_139	AC	8 ms 20,760 KB
testcase_140	AC	7 ms 20,632 KB
testcase_141	AC	7 ms 20,768 KB
testcase_142	AC	8 ms 20,900 KB
testcase_143	AC	7 ms 20,768 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;
			int lc=lca(x,y);
			dif[lc]^=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

結果

テストケース

ソースコード