#997832 (C++23) No.2822 Lights Up! (Tree Edition)

提出ソース

結果

問題	No.2822 Lights Up! (Tree Edition)
ユーザー	Aeren
提出日時	2024-07-26 22:38:55
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	63 ms / 2,000 ms
コード長	3,455 bytes
コンパイル時間	3,330 ms
コンパイル使用メモリ	261,120 KB
実行使用メモリ	21,120 KB
最終ジャッジ日時	2024-07-26 22:39:04
合計ジャッジ時間	8,297 ms
ジャッジサーバーID （参考情報）	judge1 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	60 ms 21,120 KB
testcase_03	AC	63 ms 20,992 KB
testcase_04	AC	60 ms 20,992 KB
testcase_05	AC	60 ms 20,824 KB
testcase_06	AC	61 ms 20,992 KB
testcase_07	AC	63 ms 20,992 KB
testcase_08	AC	32 ms 8,576 KB
testcase_09	AC	58 ms 19,840 KB
testcase_10	AC	45 ms 14,208 KB
testcase_11	AC	37 ms 13,312 KB
testcase_12	AC	34 ms 9,984 KB
testcase_13	AC	25 ms 6,784 KB
testcase_14	AC	41 ms 11,776 KB
testcase_15	AC	38 ms 11,776 KB
testcase_16	AC	3 ms 5,376 KB
testcase_17	AC	4 ms 5,376 KB
testcase_18	AC	7 ms 5,376 KB
testcase_19	AC	4 ms 5,376 KB
testcase_20	AC	4 ms 5,376 KB
testcase_21	AC	6 ms 5,376 KB
testcase_22	AC	6 ms 5,376 KB
testcase_23	AC	6 ms 5,376 KB
testcase_24	AC	5 ms 5,376 KB
testcase_25	AC	4 ms 5,376 KB
testcase_26	AC	6 ms 5,376 KB
testcase_27	AC	2 ms 5,376 KB
testcase_28	AC	7 ms 5,376 KB
testcase_29	AC	7 ms 5,376 KB
testcase_30	AC	6 ms 5,376 KB
testcase_31	AC	4 ms 5,376 KB
testcase_32	AC	8 ms 5,376 KB
testcase_33	AC	8 ms 5,376 KB
testcase_34	AC	8 ms 5,376 KB
testcase_35	AC	8 ms 5,376 KB
testcase_36	AC	8 ms 5,376 KB
testcase_37	AC	7 ms 5,376 KB
testcase_38	AC	8 ms 5,376 KB
testcase_39	AC	8 ms 5,376 KB
testcase_40	AC	8 ms 5,376 KB
testcase_41	AC	8 ms 5,376 KB
testcase_42	AC	8 ms 5,376 KB
testcase_43	AC	7 ms 5,376 KB
testcase_44	AC	8 ms 5,376 KB
testcase_45	AC	8 ms 5,376 KB
testcase_46	AC	7 ms 5,376 KB
testcase_47	AC	8 ms 5,376 KB
testcase_48	AC	2 ms 5,376 KB
testcase_49	AC	2 ms 5,376 KB
testcase_50	AC	2 ms 5,376 KB
testcase_51	AC	3 ms 5,376 KB
testcase_52	AC	2 ms 5,376 KB
testcase_53	AC	2 ms 5,376 KB
testcase_54	AC	3 ms 5,376 KB
testcase_55	AC	2 ms 5,376 KB
testcase_56	AC	2 ms 5,376 KB
testcase_57	AC	3 ms 5,376 KB
testcase_58	AC	2 ms 5,376 KB
testcase_59	AC	2 ms 5,376 KB
testcase_60	AC	2 ms 5,376 KB
testcase_61	AC	2 ms 5,376 KB
testcase_62	AC	3 ms 5,376 KB
testcase_63	AC	2 ms 5,376 KB
testcase_64	AC	2 ms 5,376 KB
testcase_65	AC	3 ms 5,376 KB
testcase_66	AC	2 ms 5,376 KB
testcase_67	AC	2 ms 5,376 KB
testcase_68	AC	2 ms 5,376 KB
testcase_69	AC	2 ms 5,376 KB
testcase_70	AC	2 ms 5,376 KB
testcase_71	AC	3 ms 5,376 KB
testcase_72	AC	3 ms 5,376 KB
testcase_73	AC	3 ms 5,376 KB
testcase_74	AC	3 ms 5,376 KB
testcase_75	AC	2 ms 5,376 KB
testcase_76	AC	2 ms 5,376 KB
testcase_77	AC	3 ms 5,376 KB
testcase_78	AC	2 ms 5,376 KB
testcase_79	AC	3 ms 5,376 KB
testcase_80	AC	2 ms 5,376 KB
testcase_81	AC	2 ms 5,376 KB
testcase_82	AC	2 ms 5,376 KB
testcase_83	AC	2 ms 5,376 KB
testcase_84	AC	2 ms 5,376 KB
testcase_85	AC	2 ms 5,376 KB
testcase_86	AC	2 ms 5,376 KB
testcase_87	AC	2 ms 5,376 KB
testcase_88	AC	2 ms 5,376 KB
testcase_89	AC	2 ms 5,376 KB
testcase_90	AC	2 ms 5,376 KB
testcase_91	AC	2 ms 5,376 KB
testcase_92	AC	2 ms 5,376 KB
testcase_93	AC	2 ms 5,376 KB
testcase_94	AC	2 ms 5,376 KB
testcase_95	AC	2 ms 5,376 KB
testcase_96	AC	2 ms 5,376 KB
testcase_97	AC	2 ms 5,376 KB
testcase_98	AC	2 ms 5,376 KB
testcase_99	AC	2 ms 5,376 KB
testcase_100	AC	2 ms 5,376 KB
testcase_101	AC	2 ms 5,376 KB
testcase_102	AC	2 ms 5,376 KB
testcase_103	AC	2 ms 5,376 KB
testcase_104	AC	2 ms 5,376 KB
testcase_105	AC	2 ms 5,376 KB
testcase_106	AC	2 ms 5,376 KB
testcase_107	AC	2 ms 5,376 KB
testcase_108	AC	2 ms 5,376 KB
testcase_109	AC	2 ms 5,376 KB
testcase_110	AC	2 ms 5,376 KB
testcase_111	AC	2 ms 5,376 KB
testcase_112	AC	2 ms 5,376 KB
testcase_113	AC	2 ms 5,376 KB
testcase_114	AC	2 ms 5,376 KB
testcase_115	AC	2 ms 5,376 KB
testcase_116	AC	2 ms 5,376 KB
testcase_117	AC	2 ms 5,376 KB
testcase_118	AC	2 ms 5,376 KB
testcase_119	AC	2 ms 5,376 KB
testcase_120	AC	2 ms 5,376 KB
testcase_121	AC	2 ms 5,376 KB
testcase_122	AC	2 ms 5,376 KB
testcase_123	AC	2 ms 5,376 KB
testcase_124	AC	2 ms 5,376 KB
testcase_125	AC	3 ms 5,376 KB
testcase_126	AC	2 ms 5,376 KB
testcase_127	AC	2 ms 5,376 KB
testcase_128	AC	2 ms 5,376 KB
testcase_129	AC	2 ms 5,376 KB
testcase_130	AC	2 ms 5,376 KB
testcase_131	AC	2 ms 5,376 KB
testcase_132	AC	2 ms 5,376 KB
testcase_133	AC	2 ms 5,376 KB
testcase_134	AC	2 ms 5,376 KB
testcase_135	AC	2 ms 5,376 KB
testcase_136	AC	2 ms 5,376 KB
testcase_137	AC	2 ms 5,376 KB
testcase_138	AC	2 ms 5,376 KB
testcase_139	AC	2 ms 5,376 KB
testcase_140	AC	2 ms 5,376 KB
testcase_141	AC	2 ms 5,376 KB
testcase_142	AC	2 ms 5,376 KB
testcase_143	AC	2 ms 5,376 KB

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

ソースコード

raw source code

// #include <bits/allocator.h> // Temp fix for gcc13 global pragma
// #pragma GCC target("avx2,bmi2,popcnt,lzcnt")
// #pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
// #include <x86intrin.h>
using namespace std;
#if __cplusplus >= 202002L
using namespace numbers;
#endif
#ifdef LOCAL
	#include "Debug.h"
#else
	#define debug_endl() 42
	#define debug(...) 42
	#define debug2(...) 42
	#define debugbin(...) 42
#endif

template<bool Enable_small_to_large = true>
struct disjoint_set{
#ifdef LOCAL
	#define ASSERT(x) assert(x)
#else
	#define ASSERT(x) 42
#endif
	int n, _group_count;
	vector<int> p;
	vector<list<int>> group;
	disjoint_set(){ }
	disjoint_set(int n): n(n), _group_count(n), p(n, -1), group(n){
		ASSERT(n >= 0);
		for(auto i = 0; i < n; ++ i) group[i] = {i};
	}
	int make_set(){
		p.push_back(-1);
		group.push_back(list<int>{n});
		++ _group_count;
		return n ++;
	}
	int root(int u){
		ASSERT(0 <= u && u < n);
		return p[u] < 0 ? u : p[u] = root(p[u]);
	}
	bool share(int u, int v){
		ASSERT(0 <= min(u, v) && max(u, v) < n);
		return root(u) == root(v);
	}
	int size(int u){
		ASSERT(0 <= u && u < n);
		return -p[root(u)];
	}
	bool merge(int u, int v){
		ASSERT(0 <= min(u, v) && max(u, v) < n);
		u = root(u), v = root(v);
		if(u == v) return false;
		-- _group_count;
		if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v);
		p[u] += p[v], p[v] = u;
		group[u].splice(group[u].end(), group[v]);
		return true;
	}
	bool merge(int u, int v, auto act){
		ASSERT(0 <= min(u, v) && max(u, v) < n);
		u = root(u), v = root(v);
		if(u == v) return false;
		-- _group_count;
		bool swapped = false;
		if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v), swapped = true;
		act(u, v, swapped);
		p[u] += p[v], p[v] = u;
		group[u].splice(group[u].end(), group[v]);
		return true;
	}
	int group_count() const{
		return _group_count;
	}
	const list<int> &group_of(int u){
		ASSERT(0 <= u && u < n);
		return group[root(u)];
	}
	vector<vector<int>> group_up(){
		vector<vector<int>> g(n);
		for(auto i = 0; i < n; ++ i) g[root(i)].push_back(i);
		g.erase(remove_if(g.begin(), g.end(), [&](auto &s){ return s.empty(); }), g.end());
		return g;
	}
	void clear(){
		_group_count = n;
		fill(p.begin(), p.end(), -1);
		for(auto i = 0; i < n; ++ i) group[i] = {i};
	}
	friend ostream &operator<<(ostream &out, disjoint_set dsu){
		auto gs = dsu.group_up();
		out << "{";
		if(!gs.empty()) for(auto i = 0; i < (int)gs.size(); ++ i){
			out << "{";
			for(auto j = 0; j < (int)gs[i].size(); ++ j){
				out << gs[i][j];
				if(j + 1 < (int)gs[i].size()) out << ", ";
			}
			out << "}";
			if(i + 1 < (int)gs.size()) out << ", ";
		}
		return out << "}";
	}
#undef ASSERT
};

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::badbit | ios::failbit);
	int n;
	cin >> n;
	vector<int> p(n, -1);
	vector<vector<int>> adj(n);
	for(auto u = 1; u < n; ++ u){
		cin >> p[u], -- p[u];
		adj[p[u]].push_back(u - 1);
		adj[u].push_back(u - 1);
	}
	string color;
	cin >> color;
	vector<int> init(n);
	for(auto u = 0; u < n; ++ u){
		for(auto id: adj[u]){
			init[u] ^= color[id] == '#';
		}
	}
	disjoint_set dsu(n);
	int qn;
	cin >> qn;
	for(auto qi = 0; qi < qn; ++ qi){
		int u, v;
		cin >> u >> v, -- u, -- v;
		dsu.merge(u, v);
	}
	for(auto g: dsu.group_up()){
		int par = 0;
		for(auto u: g){
			par ^= init[u];
		}
		if(par == 1){
			cout << "No\n";
			return 0;
		}
	}
	cout << "Yes\n";
	return 0;
}

/*

*/

yukicoder

結果

テストケース

ソースコード