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

提出ソース

結果

問題	No.2822 Lights Up! (Tree Edition)
ユーザー	kmjp
提出日時	2024-07-26 22:39:25
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	59 ms / 2,000 ms
コード長	1,777 bytes
コンパイル時間	2,982 ms
コンパイル使用メモリ	213,020 KB
実行使用メモリ	16,908 KB
最終ジャッジ日時	2024-07-26 22:39:34
合計ジャッジ時間	7,987 ms
ジャッジサーバーID （参考情報）	judge3 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	5 ms 12,512 KB
testcase_01	AC	5 ms 12,520 KB
testcase_02	AC	54 ms 16,484 KB
testcase_03	AC	55 ms 16,488 KB
testcase_04	AC	47 ms 15,972 KB
testcase_05	AC	51 ms 16,224 KB
testcase_06	AC	52 ms 16,908 KB
testcase_07	AC	59 ms 16,352 KB
testcase_08	AC	34 ms 13,800 KB
testcase_09	AC	51 ms 15,720 KB
testcase_10	AC	51 ms 15,716 KB
testcase_11	AC	32 ms 14,436 KB
testcase_12	AC	35 ms 14,052 KB
testcase_13	AC	42 ms 15,076 KB
testcase_14	AC	59 ms 16,740 KB
testcase_15	AC	38 ms 14,308 KB
testcase_16	AC	6 ms 12,516 KB
testcase_17	AC	7 ms 12,644 KB
testcase_18	AC	10 ms 12,772 KB
testcase_19	AC	7 ms 12,516 KB
testcase_20	AC	7 ms 12,516 KB
testcase_21	AC	10 ms 12,896 KB
testcase_22	AC	9 ms 12,900 KB
testcase_23	AC	8 ms 12,648 KB
testcase_24	AC	8 ms 12,644 KB
testcase_25	AC	6 ms 12,648 KB
testcase_26	AC	8 ms 12,772 KB
testcase_27	AC	6 ms 12,516 KB
testcase_28	AC	10 ms 12,776 KB
testcase_29	AC	13 ms 13,160 KB
testcase_30	AC	9 ms 12,896 KB
testcase_31	AC	7 ms 12,644 KB
testcase_32	AC	9 ms 12,900 KB
testcase_33	AC	10 ms 12,900 KB
testcase_34	AC	10 ms 12,900 KB
testcase_35	AC	9 ms 12,900 KB
testcase_36	AC	11 ms 12,896 KB
testcase_37	AC	8 ms 12,768 KB
testcase_38	AC	11 ms 12,896 KB
testcase_39	AC	11 ms 12,900 KB
testcase_40	AC	10 ms 12,776 KB
testcase_41	AC	10 ms 12,900 KB
testcase_42	AC	10 ms 13,156 KB
testcase_43	AC	9 ms 12,772 KB
testcase_44	AC	10 ms 12,904 KB
testcase_45	AC	10 ms 13,032 KB
testcase_46	AC	10 ms 12,904 KB
testcase_47	AC	13 ms 13,152 KB
testcase_48	AC	8 ms 12,516 KB
testcase_49	AC	7 ms 12,384 KB
testcase_50	AC	6 ms 12,388 KB
testcase_51	AC	6 ms 12,516 KB
testcase_52	AC	6 ms 12,388 KB
testcase_53	AC	7 ms 12,388 KB
testcase_54	AC	6 ms 12,516 KB
testcase_55	AC	6 ms 12,384 KB
testcase_56	AC	6 ms 12,516 KB
testcase_57	AC	5 ms 12,512 KB
testcase_58	AC	6 ms 12,520 KB
testcase_59	AC	7 ms 12,520 KB
testcase_60	AC	7 ms 12,516 KB
testcase_61	AC	7 ms 12,520 KB
testcase_62	AC	6 ms 12,512 KB
testcase_63	AC	6 ms 12,384 KB
testcase_64	AC	6 ms 12,516 KB
testcase_65	AC	6 ms 12,512 KB
testcase_66	AC	5 ms 12,388 KB
testcase_67	AC	6 ms 12,512 KB
testcase_68	AC	6 ms 12,516 KB
testcase_69	AC	6 ms 12,388 KB
testcase_70	AC	6 ms 12,640 KB
testcase_71	AC	7 ms 12,516 KB
testcase_72	AC	5 ms 12,520 KB
testcase_73	AC	5 ms 12,388 KB
testcase_74	AC	6 ms 12,384 KB
testcase_75	AC	6 ms 12,512 KB
testcase_76	AC	6 ms 12,388 KB
testcase_77	AC	5 ms 12,516 KB
testcase_78	AC	7 ms 12,384 KB
testcase_79	AC	6 ms 12,516 KB
testcase_80	AC	6 ms 12,388 KB
testcase_81	AC	6 ms 12,388 KB
testcase_82	AC	6 ms 12,384 KB
testcase_83	AC	6 ms 12,516 KB
testcase_84	AC	6 ms 12,388 KB
testcase_85	AC	6 ms 12,516 KB
testcase_86	AC	6 ms 12,516 KB
testcase_87	AC	5 ms 12,384 KB
testcase_88	AC	6 ms 12,388 KB
testcase_89	AC	5 ms 12,512 KB
testcase_90	AC	6 ms 12,516 KB
testcase_91	AC	5 ms 12,516 KB
testcase_92	AC	6 ms 12,516 KB
testcase_93	AC	6 ms 12,516 KB
testcase_94	AC	6 ms 12,388 KB
testcase_95	AC	6 ms 12,512 KB
testcase_96	AC	6 ms 12,392 KB
testcase_97	AC	6 ms 12,512 KB
testcase_98	AC	6 ms 12,516 KB
testcase_99	AC	5 ms 12,644 KB
testcase_100	AC	6 ms 12,388 KB
testcase_101	AC	5 ms 12,520 KB
testcase_102	AC	5 ms 12,516 KB
testcase_103	AC	6 ms 12,388 KB
testcase_104	AC	6 ms 12,388 KB
testcase_105	AC	5 ms 12,388 KB
testcase_106	AC	6 ms 12,388 KB
testcase_107	AC	6 ms 12,520 KB
testcase_108	AC	6 ms 12,512 KB
testcase_109	AC	6 ms 12,392 KB
testcase_110	AC	6 ms 12,388 KB
testcase_111	AC	6 ms 12,512 KB
testcase_112	AC	6 ms 12,388 KB
testcase_113	AC	6 ms 12,388 KB
testcase_114	AC	7 ms 12,512 KB
testcase_115	AC	6 ms 12,512 KB
testcase_116	AC	6 ms 12,516 KB
testcase_117	AC	6 ms 12,520 KB
testcase_118	AC	6 ms 12,516 KB
testcase_119	AC	6 ms 12,392 KB
testcase_120	AC	5 ms 12,516 KB
testcase_121	AC	6 ms 12,516 KB
testcase_122	AC	7 ms 12,516 KB
testcase_123	AC	6 ms 12,512 KB
testcase_124	AC	6 ms 12,384 KB
testcase_125	AC	5 ms 12,648 KB
testcase_126	AC	5 ms 12,392 KB
testcase_127	AC	7 ms 12,384 KB
testcase_128	AC	6 ms 12,388 KB
testcase_129	AC	6 ms 12,388 KB
testcase_130	AC	6 ms 12,520 KB
testcase_131	AC	7 ms 12,392 KB
testcase_132	AC	6 ms 12,516 KB
testcase_133	AC	7 ms 12,520 KB
testcase_134	AC	7 ms 12,520 KB
testcase_135	AC	6 ms 12,516 KB
testcase_136	AC	5 ms 12,516 KB
testcase_137	AC	5 ms 12,512 KB
testcase_138	AC	7 ms 12,512 KB
testcase_139	AC	5 ms 12,388 KB
testcase_140	AC	7 ms 12,388 KB
testcase_141	AC	7 ms 12,392 KB
testcase_142	AC	6 ms 12,392 KB
testcase_143	AC	6 ms 12,644 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[200005],D[202020];
int L[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[cur]) D[e]=D[cur]+1, P[e]=cur, dfs(e);
	L[cur]=id++;
	re[L[cur]]=cur;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	for(i=1;i<N;i++) {
		cin>>x;
		E[x-1].push_back(i);
	}
	cin>>S;
	dfs(0);
	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[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

結果

テストケース

ソースコード