Submission #1162400

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162400		The_Samurai	디지털 회로 (IOI22_circuit)	C++17	22 / 100	3042 ms	8888 KiB

circuit

#include "circuit.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define ff first
#define ss second
const int mod = 1'000'002'022;

void upd(ll &a, ll b) {
    a = (a + b) % mod;
    if (a < 0) a += mod;
}

int n, m;
vector<int> a, p, height;
vector<vector<int>> g;
vector<array<ll, 2>> dp;

void calc(int u) {
    vector<ll> now(g[u].size() + 1);
    now[0] = 1;
    for (int v: g[u]) {
        vector<ll> nw(g[u].size() + 1);
        for (int i = g[u].size() - 1; i >= 0; i--) {
            upd(nw[i + 1], now[i] * dp[v][1]);
            upd(nw[i], now[i] * dp[v][0]);
        }
        swap(nw, now);
    }
    dp[u][0] = dp[u][1] = 0;
    ll sum0 = accumulate(now.begin(), now.end(), 0ll) % mod, sum1 = 0;
    for (int i = g[u].size(); i > 0; i--) {
        upd(sum1, now[i]); upd(sum0, -now[i]);
        upd(dp[u][1], sum1);
        upd(dp[u][0], sum0);
    }
}

void dfs(int u) {
    if (u >= n) {
        dp[u][a[u - n]] = 1; dp[u][!a[u - n]] = 0;
        return;
    }

    for (int v: g[u]) {
        height[v] = height[u] + 1;
        dfs(v);
    }
    calc(u);
}

void init(int _n, int _m, std::vector<int> P, std::vector<int> A) {
    n = _n, m = _m;
    a = A; p = P;
    g.assign(n, {});
    height.assign(n + m, 0);
    dp.assign(n + m, array<ll, 2>{});
    for (int i = 1; i < n + m; i++) g[p[i]].emplace_back(i);
    dfs(0);
}

int count_ways(int L, int R) {
    priority_queue<pair<int, int>> pq;
    set<int> vis;
    for (int i = L; i <= R; i++) {
        a[i - n] = !a[i - n];
        dp[i][a[i - n]] = 1; dp[i][!a[i - n]] = 0;  
        pq.emplace(height[p[i]], p[i]);
    }
    while (!pq.empty()) {
        auto [_, u] = pq.top(); pq.pop();
        if (vis.count(u)) continue;
        vis.insert(u);
        calc(u);
        if (u > 0) pq.emplace(height[p[u]], p[u]);
    }
    return dp[0][1];
}

• Subtask 1: 2 / 2
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 4 / 4
• Subtask 5: 0 / 12
• Subtask 6: 0 / 27
• Subtask 7: 0 / 28
• Subtask 8: 0 / 11