Submission #825750

#	Time	Username	Problem	Language	Result	Execution time	Memory
825750		becaido	Digital Circuit (IOI22_circuit)	C++17	0 / 100	346 ms	4968 KiB

circuit

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "circuit.h"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int MOD = 1000002022;
const int SIZE = 1e5 + 5;

int n, m, ans;
vector<int> adj[SIZE];
int a[SIZE], coef[SIZE], all[SIZE];

void pre(int pos) {
    int pro = 1;
    for (int np : adj[pos]) {
        pre(np);
        pro = 1ll * pro * all[np] % MOD;
    }
    if (adj[pos].size()) pro = 1ll * pro * adj[pos].size() % MOD;
    all[pos] = pro;
}
void dfs(int pos, int cur) {
    if (adj[pos].size() == 0) {
        coef[pos - n] = cur;
        return;
    }
    assert(adj[pos].size() == 2);
    dfs(adj[pos][0], 1ll * cur * all[adj[pos][1]] % MOD);
    dfs(adj[pos][1], 1ll * cur * all[adj[pos][0]] % MOD);
}

void init(int N, int M, vector<int> P, vector<int> A) {
    n = N, m = M;
    FOR (i, 1, n + m - 1) adj[P[i]].pb(i);
    pre(0);
    dfs(0, 1);
    FOR (i, 0, m - 1) {
        a[i] = A[i];
        if (a[i]) ans = (ans + coef[i]) % MOD;
    }
}

int count_ways(int L, int R) {
    a[L] ^= 1;
    if (a[L] == 0) ans -= coef[L];
    else ans += coef[L];
    if (ans >= MOD) ans -= MOD;
    if (ans < 0) ans += MOD;
    return ans;
}

/*
in1
3 4 3
-1 0 1 2 1 1 0
1 0 1 0
3 4
4 5
3 6
out1
2
0
6
*/

#ifdef WAIMAI
int main() {
  int N, M, Q;
  assert(3 == scanf("%d %d %d", &N, &M, &Q));
  vector<int> P(N + M), A(M);
  for (int i = 0; i < N + M; ++i) {
    assert(1 == scanf("%d", &P[i]));
  }
  for (int j = 0; j < M; ++j) {
    assert(1 == scanf("%d", &A[j]));
  }
  init(N, M, P, A);

  for (int i = 0; i < Q; ++i) {
    int L, R;
    assert(2 == scanf("%d %d", &L, &R));
    printf("%d\n", count_ways(L, R));
  }
  return 0;
}
#endif

• Subtask 1: 0 / 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