結果

問題 No.2822 Lights Up! (Tree Edition)
ユーザー Astral__
提出日時 2024-07-26 23:54:48
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,021 bytes
コンパイル時間 9,961 ms
コンパイル使用メモリ 556,784 KB
実行使用メモリ 25,124 KB
最終ジャッジ日時 2024-07-26 23:55:11
合計ジャッジ時間 22,272 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 88 WA * 54
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/rational.hpp>

// 任意長整数型
using Bint = boost::multiprecision::cpp_int;
// 仮数部が10進数で1024桁の浮動小数点数型(TLEしたら小さくする)
using Real =
    boost::multiprecision::number<boost::multiprecision::cpp_dec_float<1024>>;
using Rat = boost::rational<Bint>;

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
TT using vvec = vec<vec<T>>;
TT using vvvec = vec<vvec<T>>;
TT using minheap = priority_queue<T, vector<T>, greater<T>>;
TT using maxheap = priority_queue<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
TT auto prev_itr(vec<T> &A, T x) {  // must sorted
    auto res = lower_bound(all(A), x);
    if (res == A.begin())
        return A.end();
    else
        return --res;
}
TT auto next_itr(vec<T> &A, T x) {  // must sorted
    return upper_bound(all(A), x) - A.begin();
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

int main() {
    ll n;
    cin >> n;
    vec<vec<int>> g(n);
    rep(i, 1, n) {
        int p;
        cin >> p;
        p--;
        g[i].push_back(p);
        g[p].push_back(i);
    }

    vec<int> col(n, 0);
    rep(i, 1, n) {
        char c;
        cin >> c;
        if (c == '#') col[i] = 1; //変える必要がある。
    }

    ll k;
    cin >> k;
    vec<int> U(k), V(k);
    rep(i, 0, k) {
        cin >> U[i] >> V[i];
        U[i]--, V[i]--;
    }
    vec<set<int>> rev(n);
    rep(i, 0, k) {
        rev[U[i]].insert(i);
        rev[V[i]].insert(i);
    }


    vec<int> base(n, -1);

    auto path_xor = [&](int v, int id1, int id2) {  // id2を変更する。
     
        int nl, nr;
        if (U[id1] == v)
            nl = V[id1];
        else
            nl = U[id1];

        if (U[id2] == v)
            nr = V[id2];
        else
            nr = U[id2];

        rev[U[id2]].erase(id2);
        rev[V[id2]].erase(id2);
        U[id2] = nl;
        V[id2] = nr;
        if (nl == nr) return;

        rev[U[id2]].insert(id2);
        rev[V[id2]].insert(id2);
        return;
    };

    set<int> base_used;

    auto dfs = [&](auto f, int v, int p = -1) -> void {
        for(int to : g[v]) if(to != p) {
            f(f, to, v);
        }

        int use = -1;
        for(int id : rev[v]) if(base_used.count(id) == 0) use = id;
        if(use == -1) return;

        base_used.insert(use);
        vec<int> tar;
        for(int id : rev[v]) if(id != use) tar.push_back(id);
        sort(all(tar));
        tar.erase(unique(all(tar)), tar.end());
        for(int id : tar) path_xor(v, use, id);
        /*
        vec<int> era;
        for(int di : rev[v]) era.push_back(di);

        for(int di : era) path_xor(v, use, di);
        */

        base[v] = use;
        return;
    };

    dfs(dfs, 0);

    vec<int> imos(n, 0);

    set<int> already;

    rep(i, 0, n) if(base[i] != -1 && col[i] == 1 && !already.count(base[i])) {
        int id = base[i];
        already.insert(id);

        imos[U[id]]++;
        imos[V[id]]++;
    }

    auto dfs2 = [&](auto f, int v, int p = -1) -> bool {
        for(int to : g[v]) if(to != p) {
            if(f(f, to, v) == false) {
                return false;
            }
        }

        if(p != -1) imos[p] += imos[v];

        if((imos[v] % 2) != col[v]) {
            return false;
        }
        else return true;
    };


    if(dfs2(dfs2, 0)) cout <<  "Yes" << endl;
    else cout << "No" << endl;


}
0