제출 #1025197

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1025197		vjudge1	디지털 회로 (IOI22_circuit)	C++17	100 / 100	879 ms	82340 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>

using namespace std;

#define rall(s) s.rbegin(), s.rend()
#define all(s) s.begin(), s.end()
#define sz(s) (int) s.size()
#define s second 
#define f first 

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int N = 1e6, mod = 1000002022;

int n, m, is = 1;
vector<int> g[N], a(N);

vector<ll> pr(N), sf(N), val(N), gvl(N);

void calc(int u) {
    for (int to: g[u]) {
        calc(to);
    }
    int M = sz(g[u]);
    if (!M) {
        val[u] = 1;
        return;
    }
    for (int i = 0; i < M; i++) {
        if (i) pr[i] = pr[i - 1];
        else pr[i] = 1;
        pr[i] = (pr[i] * val[g[u][i]]) % mod;
    }
    for (int i = M - 1; i >= 0; i--) {
        if (i < M - 1) sf[i] = sf[i + 1];
        else sf[i] = 1;
        sf[i] = (sf[i] * val[g[u][i]]) % mod; 
    }
    for (int i = 0; i < M; i++) {
        gvl[g[u][i]] = ((i ? pr[i - 1] : 1ll) * (i < M - 1 ? sf[i + 1] : 1ll)) % mod;
    }
    val[u] = (pr[M - 1] * M) % mod;
}

ll vl[N];

void dfs(int u, int x) {
    int M = sz(g[u]);
    if (!M) {
        vl[u - n] = x;
        return;
    }
    for (int to: g[u]) {
        dfs(to, (x * gvl[to]) % mod);
    }
}

pll t[4 * N];
int swp[4 * N];

void bld(int u = 1, int tl = 0, int tr = m - 1) {
    if (tl == tr) {
        if (a[tl]) t[u].f = vl[tl];
        else t[u].s = vl[tl];
        return;
    }
    int mid = (tl + tr) / 2;
    bld(u * 2, tl, mid);
    bld(u * 2 + 1, mid + 1, tr);
    t[u].f = (t[u * 2].f + t[u  * 2 + 1].f) % mod;
    t[u].s = (t[u * 2].s + t[u  * 2 + 1].s) % mod;
}

void push(int u, int tl, int tr) {
    if (!swp[u]) return;
    swap(t[u].f, t[u].s);
    if (tl < tr) {
        swp[u * 2] ^= 1;
        swp[u * 2 + 1] ^= 1;
    }
    swp[u] = 0;
}

void upd(int l, int r, int u = 1, int tl = 0, int tr = m - 1) {
    push(u, tl, tr);
    if (tl > r || tr < l) return;
    if (tl >= l && tr <= r) {
        swp[u] = 1;
        push(u, tl, tr);
        return;
    }
    int mid = (tl + tr) / 2;
    upd(l, r, u * 2, tl, mid);
    upd(l, r, u * 2 + 1, mid + 1, tr);    
    t[u].f = (t[u * 2].f + t[u  * 2 + 1].f) % mod;
    t[u].s = (t[u * 2].s + t[u  * 2 + 1].s) % mod;
}


void init(int nn, int M, vector<int> P, vector<int> A) {
    n = nn, m = M;
    for (int i = 0; i < m; i++) a[i] = A[i];
    for (int i = 1; i < n + m; i++) g[P[i]].push_back(i);
    calc(0), dfs(0, 1), bld();
}

int count_ways(int l, int r) {
    upd(l - n, r - n);
    return t[1].f;
}

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