結果

問題 No.2822 Lights Up! (Tree Edition)
ユーザー 🦠みどりむし🦠みどりむし
提出日時 2024-06-18 19:43:17
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,434 bytes
コンパイル時間 1,967 ms
コンパイル使用メモリ 152,016 KB
実行使用メモリ 23,572 KB
最終ジャッジ日時 2024-06-18 19:46:57
合計ジャッジ時間 7,329 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other AC * 77 WA * 65
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <ranges>
#include <valarray>
#include <string>

#include <atcoder/dsu>

struct Edge {
    long long to;
};

using Graph = std::vector<std::vector<Edge>>;

struct LCA {
    std::vector<std::vector<int>> parent;
    std::vector<int> dist;
    LCA(const Graph &G, int root = 0) { init(G, root); }

    void init(const Graph &G, int root = 0) {
        int V = G.size();
        int K = 1;
        while ((1 << K) < V) K++;
        parent.assign(K, std::vector<int>(V, -1));
        dist.assign(V, -1);
        dfs(G, root, -1, 0);
        for (int k = 0; k + 1 < K; k++) {
            for (int v = 0; v < V; v++) {
                if (parent[k][v] < 0) {
                    parent[k + 1][v] = -1;
                } else {
                    parent[k + 1][v] = parent[k][parent[k][v]];
                }
            }
        }
    }

    void dfs(const Graph &G, int v, int p, int d) {
        parent[0][v] = p;
        dist[v] = d;
        for (auto e : G[v]) {
            if (e.to != p) dfs(G, e.to, v, d + 1);
        }
    }

    int query(int u, int v) {
        if (dist[u] < dist[v]) std::swap(u, v);
        int K = parent.size();

        for (int k = 0; k < K; k++) {
            if ((dist[u] - dist[v]) >> k & 1) {
                u = parent[k][u];
            }
        }

        if (u == v) return u;
        for (int k = K - 1; k >= 0; k--) {
            if (parent[k][u] != parent[k][v]) {
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }
};


signed main() {
	int n; std::cin >> n;

	std::valarray<int> p(n);
    Graph tree(n);
	for(auto i : std::views::iota(1, n)) {
        std::cin >> p[i], --p[i];
        tree[p[i]].emplace_back(i), tree[i].emplace_back(p[i]);
    }

    LCA lca(tree, n - 1);

	std::valarray<bool> v(n);
	std::string s; std::cin >> s;
	for(const auto i : std::views::iota(1, n)) v[i] = s[i - 1] == '#';

	atcoder::dsu ds(n);

	int q; std::cin >> q;
	for(const auto _ : std::views::iota(0, q)) {
		int x, y; std::cin >> x >> y; --x, --y;
        ds.merge(x, lca.query(x, y));
        ds.merge(x, lca.query(x, y));
	}

	for(const auto i : std::views::iota(1, n)) {
		v[p[i]] ^= s[i - 1] == '#';
	}

	for(const auto& group : ds.groups()) {
		bool x = false;
		for(const auto i : group) x ^= v[i];

		if(x) {
			std::cout << "No" << "\n";
			return 0;
		}
	}

	std::cout << "Yes" << "\n";
}
0