제출 #869245

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
869245		abcvuitunggio	Digital Circuit (IOI22_circuit)	C++17	100 / 100	681 ms	34732 KiB

circuit

#include "circuit.h"
#include <vector>
using namespace std;
const int mod=1000002022;
struct T{
    int sum,val;
}st[800001];
T operator +(T a, T b){
    return {(a.sum+b.sum)%mod,(a.val+b.val)%mod};
}
int n,a[200001],b[200001],lazy[800001],c[200001];
void down(int node, int l, int r){
    if (!lazy[node]||l==r)
        return;
    st[node<<1].val=(st[node<<1].sum-st[node<<1].val+mod)%mod;
    lazy[node<<1]^=1;
    st[node<<1|1].val=(st[node<<1|1].sum-st[node<<1|1].val+mod)%mod;
    lazy[node<<1|1]^=1;
    lazy[node]=0;
}
void build(int node, int l, int r){
    if (l==r){
        st[node]={b[l],a[l]*b[l]};
        return;
    }
    int mid=(l+r)>>1;
    build(node<<1,l,mid);
    build(node<<1|1,mid+1,r);
    st[node]=st[node<<1]+st[node<<1|1];
}
void update(int node, int l, int r, int u, int v){
    if (l>v||r<u||l>r||u>v)
        return;
    if (l>=u&&r<=v){
        lazy[node]^=1;
        st[node].val=(st[node].sum-st[node].val+mod)%mod;
        return;
    }
    down(node,l,r);
    int mid=(l+r)>>1;
    update(node<<1,l,mid,u,v);
    update(node<<1|1,mid+1,r,u,v);
    st[node]=st[node<<1]+st[node<<1|1];
}
vector <int> ke[200001];
void dfs(int u){
    if (ke[u].empty()){
        c[u]=1;
        return;
    }
    c[u]=ke[u].size();
    for (int v:ke[u]){
        dfs(v);
        c[u]=1LL*c[u]*c[v]%mod;
    }
}
void dfs2(int u, int val){
    if (ke[u].empty()){
        b[u]=val;
        return;
    }
    int d[ke[u].size()];
    for (int i=0;i<ke[u].size();i++)
        d[i]=1LL*(i?d[i-1]:1)*c[ke[u][i]]%mod;
    int cur=1;
    for (int i=ke[u].size()-1;i>=0;i--){
        dfs2(ke[u][i],(1LL*cur*(i?d[i-1]:1)%mod*val)%mod);
        cur=1LL*cur*c[ke[u][i]]%mod;
    }
}
void init(int N, int M, vector <int> P, vector <int> A){
    n=N+M;
    for (int i=0;i<M;i++)
        a[N+i]=A[i];
    for (int i=1;i<N+M;i++)
        ke[P[i]].push_back(i);
    dfs(0);
    dfs2(0,1);
    build(1,0,n-1);
}
int count_ways(int L, int R){
    update(1,0,n-1,L,R);
    return st[1].val;
}

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

circuit.cpp: In function 'void dfs2(int, int)':
circuit.cpp:63:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for (int i=0;i<ke[u].size();i++)
      |                  ~^~~~~~~~~~~~~

• 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