Submission #1080477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080477		The_Samurai	Digital Circuit (IOI22_circuit)	C++17	2 / 100	467 ms	4668 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;
}

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

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

    for (int u = n - 1; u >= 0; u--) {
        vector<ll> old(child[u].size() + 1);
        old[0] = 1;
        ll all = child[u].size();
        for (int v: child[u]) {
            vector<ll> nw(child[u].size() + 1);
            all = all * (dp[v][0] + dp[v][1]) % mod;
            for (int i = 0; i < child[u].size(); i++) {
                upd(nw[i], old[i] * dp[v][0]);
                upd(nw[i + 1], old[i] * dp[v][1]);
            }
            old = nw;
        }
        for (int i = 1; i <= child[u].size(); i++) {
            upd(dp[u][1], old[i] * i);
        }
        dp[u][0] = (all - dp[u][1] + mod) % mod;
    }
}

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] = !a[i];
        swap(dp[i][0], dp[i][1]);
        if (vis.count(p[i])) continue;
        pq.emplace(height[p[i]], p[i]);
        vis.insert(p[i]);
    }

    while (!pq.empty()) {
        auto [h, u] = pq.top(); pq.pop();
        // cout << '\t' << h << ' ' << u << endl;
        vector<ll> old(child[u].size() + 1);
        old[0] = 1;
        ll all = child[u].size();
        dp[u][0] = dp[u][1] = 0;
        for (int v: child[u]) {
            vector<ll> nw(child[u].size() + 1);
            all = all * (dp[v][0] + dp[v][1]) % mod;
            for (int i = 0; i < child[u].size(); i++) {
                upd(nw[i], old[i] * dp[v][0]);
                upd(nw[i + 1], old[i] * dp[v][1]);
            }
            old = nw;
        }
        for (int i = 1; i <= child[u].size(); i++) {
            upd(dp[u][1], old[i] * i);
        }
        dp[u][0] = (all - dp[u][1] + mod) % mod;

        if (vis.count(p[u]) or u == 0) continue;
        vis.insert(p[u]);
        pq.emplace(height[p[u]], p[u]);
    }
    return dp[0][1];
}

Compilation message (stderr)

circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:36:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |             for (int i = 0; i < child[u].size(); i++) {
      |                             ~~^~~~~~~~~~~~~~~~~
circuit.cpp:42:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for (int i = 1; i <= child[u].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~
circuit.cpp: In function 'int count_ways(int, int)':
circuit.cpp:70:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |             for (int i = 0; i < child[u].size(); i++) {
      |                             ~~^~~~~~~~~~~~~~~~~
circuit.cpp:76:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for (int i = 1; i <= child[u].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~

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