제출 #653499

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
653499		Lobo	디지털 회로 (IOI22_circuit)	C++17	2 / 100	3086 ms	8196 KiB

circuit

#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 2e5+10;
const int mod = 1000002022;
int n, m, p[maxn], a[maxn];
vector<int> g[maxn];
int c[maxn], pw2[maxn], prd[maxn];
int32_t tr0[4*maxn],tr1[4*maxn],lz[4*maxn];

void build(int no, int l, int r) {
    if(l == r) {
        tr0[no] = (a[l-n] == 0)*prd[l];
        tr1[no] = (a[l-n] == 1)*prd[l];
        return;
    }
    int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
    build(f1,l,mid);
    build(f2,mid+1,r);
    tr0[no] = (tr0[f1]+tr0[f2])%mod;
    tr1[no] = (tr1[f1]+tr1[f2])%mod;
}

void flush(int no, int l, int r) {
    if(lz[no] == 0) return;
    swap(tr0[no],tr1[no]);
    if(l != r) {
        int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
        lz[f1]^= 1;
        lz[f2]^= 1;
    }
    lz[no] = 0;
}

void att(int no, int l, int r, int L, int R) {
    flush(no,l,r);
    if(l > R || r < L) return;
    if(l >= L && r <= R) {
        lz[no] = 1;
        flush(no,l,r);
        return;
    }
    int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
    att(f1,l,mid,L,R);
    att(f2,mid+1,r,L,R);
    tr0[no] = (tr0[f1]+tr0[f2])%mod;
    tr1[no] = (tr1[f1]+tr1[f2])%mod;
}

void dfssz(int u) {
    c[u] = g[u].size();
    if(u >= n) c[u] = 1;
    if(u >= n) return;
    for(auto v : g[u]) {
        dfssz(v);
        c[u] = c[u]*c[v]%mod;
    }
}

void dfs(int u) {
    vector<int> pf(g[u].size()+1), sf(g[u].size()+1);

    for(int i = 0; i < (int) g[u].size(); i++) {
        int v = g[u][i];
        pf[i] = c[v];
        if(i!=0) pf[i] = pf[i]*pf[i-1]%mod;
    }
    for(int i = (int) g[u].size()-1; i >= 0; i--) {
        int v = g[u][i];
        sf[i] = c[v];
        if(i != (int) g[u].size()-1) sf[i] = sf[i]*sf[i+1]%mod;
    }

    for(int i = 0; i < (int) g[u].size(); i++) {
        int v = g[u][i];
        prd[v] = prd[u];
        if(i != 0) prd[v] = prd[v]*pf[i-1]%mod;
        if(i != (int) g[u].size()-1) prd[v] = prd[v]*sf[i+1]%mod;
        dfs(v);
    }

    for(auto v : g[u]) {
        dfs(v);
    }
}

int ans = 0;
void init(int32_t N, int32_t M, vector<int32_t> P, vector<int32_t> A) {
    n = N;
    m = M;
    for(int i = 1; i < n+m; i++) {
        p[i] = P[i];
        g[p[i]].pb(i);
    }
    for(int i = 0; i < m; i++) {
        a[i] = A[i];
    }
    dfssz(0);
    prd[0] = 1;
    dfs(0);
    build(1,n,n+m-1);
}
int32_t count_ways(int32_t L, int32_t R) {
    att(1,n,n+m-1,L,R);
    return tr1[1];
}

컴파일 시 표준 에러 (stderr) 메시지

circuit.cpp: In function 'void flush(long long int, long long int, long long int)':
circuit.cpp:37:31: warning: unused variable 'mid' [-Wunused-variable]
   37 |         int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
      |                               ^~~

• 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