結果
問題 | No.2822 Lights Up! (Tree Edition) |
ユーザー |
|
提出日時 | 2024-07-26 22:38:55 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 142 |
ソースコード
// #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; } /* */