oj.uz

Submission #628048

# Submission time Handle Problem Language Result Execution time Memory
628048 2022-08-13T03:58:46 Z czhang2718 Digital Circuit (IOI22_circuit) C++17
0 / 100
 750 ms 8444 KB 
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;

const int mod=1e9+2022;
const int N=2e5;
int n, m, q;
vector<int> adj[N];
int p[N];
int a[N];
int sum[4*N], con[4*N], c[N];
ll prod[N];

int add(int a, int b){
    return ((a+mod)%mod+(b+mod)%mod)%mod;
}

void add2(int &a, int b){
    a=add(a,b);
}

int mult(ll a, ll b){
    return (a*b)%mod;
}

void mult2(ll &a, ll b){
    a=mult(a,b);
}

void dfs(int x){
    prod[x]=x<n?adj[x].size():1;
    for(int k:adj[x]){
        dfs(k);
        mult2(prod[x], prod[k]);
    }
}

void dfs2(int x){
    int p=adj[x].size();
    vector<ll> pre(p), suf(p);
    for(int i=0; i<p; i++){
        int k=adj[x][i];
        pre[i]=suf[i]=prod[k];
    }
    for(int i=1; i<p; i++){
        mult2(pre[i], pre[i-1]);
    }
    for(int i=p-2; i>=0; i--){
        mult2(suf[i], suf[i+1]);
    }

    for(int i=0; i<p; i++){
        int k=adj[x][i];
        c[k]=mult(c[x], mult(i?pre[i-1]:1, i<p-1?suf[i+1]:1));
        dfs2(k);
    }
}

short lazy[4*N];

void build(int x, int lx, int rx){
    if(rx-lx==1){
        con[x]=a[lx]?c[lx+n]:0;
        // cout << "c[" << lx+n << "] " << c[lx+n] << "\n";
        sum[x]=c[lx+n];
        return;
    }
    int m=(lx+rx)/2;
    build(2*x+1, lx, m);
    build(2*x+2, m, rx);
    con[x]=add(con[2*x+1], con[2*x+2]);
    sum[x]=add(sum[2*x+1], sum[2*x+2]);
}

void push(int x, int lx, int rx){
    if(rx-lx==1 || !lazy[x]) return;
    for(int y=2*x+1; y<=2*x+2; y++){
        con[y]=sum[y]-con[y];
        lazy[y]^=1;
    }
    lazy[x]=0;
}

void tog(int l, int r, int x=0, int lx=0, int rx=m){
    push(x, lx, rx);
    if(lx>=r || rx<=l) return;
    if(lx>=l && rx<=r){
        con[x]=sum[x]-con[x];
        lazy[x]=1;
        return;
    }
    int m=(lx+rx)/2;
    tog(l, r, 2*x+1, lx, m);
    tog(l, r, 2*x+2, m, rx);
    con[x]=add(con[2*x+1], con[2*x+2]);
}

void init(int n, int m, std::vector<int> P, std::vector<int> A) {
  for(int i=0; i<n+m; i++){
      p[i]=P[i];
      if(i) adj[p[i]].push_back(i);
  }
  for(int i=0; i<m; i++) a[i]=A[i];

  dfs(0);
  c[0]=1;
  dfs2(0);

  build(0, 0, m);
}

int count_ways(int l, int r) {
  l-=n; r-=n;
  tog(l, r+1);
  return con[0];
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4944 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4944 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4944 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 750 ms 8444 KB 1st lines differ - on the 1st token, expected: '431985922', found: '16401'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 750 ms 8444 KB 1st lines differ - on the 1st token, expected: '431985922', found: '16401'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4944 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4944 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4944 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -