Submission #736752

#	Time	Username	Problem	Language	Result	Execution time	Memory
736752		onlk97	Digital Circuit (IOI22_circuit)	C++17	13 / 100	950 ms	14628 KiB

circuit

#include "circuit.h"
 
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const long long mod=1e9+2022LL;
vector <int> g[200010];
long long sz[200010],d[200010],ac[200010];
int n,dif;
long long weight[100010],a[100010],weightps[100010],seg[400040],laz[400010];
bool marked[100010];
void dfs1(int cur){
    sz[cur]=g[cur].size();
    sz[cur]=max(sz[cur],1LL);
    for (int i:g[cur]){
        dfs1(i);
        sz[cur]*=sz[i];
        sz[cur]%=mod;
    }
    if (!g[cur].size()){
        return;
    } else {
        int fr[g[cur].size()],ba[g[cur].size()];
        for (int i=0; i<g[cur].size(); i++){
            if (!i) fr[i]=sz[g[cur][i]];
            else fr[i]=fr[i-1]*sz[g[cur][i]]%mod;
        }
        for (int i=g[cur].size()-1; i>=0; i--){
            if (i==g[cur].size()-1) ba[i]=sz[g[cur][i]];
            else ba[i]=ba[i+1]*sz[g[cur][i]]%mod;
        }
        for (int i=0; i<g[cur].size(); i++){
            int t=1;
            if (i) t=t*fr[i-1]%mod;
            if (i+1<g[cur].size()) t=t*ba[i+1]%mod;
            d[g[cur][i]]=t;
        }
    }
}
void dfs2(int cur){
    for (int i:g[cur]){
        ac[i]=ac[cur]*d[i]%mod;
        dfs2(i);
    }
}
void build(int id,int tl,int tr){
    if (tl==tr){
        seg[id]=a[tl]*weight[tl];
        return;
    }
    int tm=(tl+tr)/2;
    build(2*id,tl,tm);
    build(2*id+1,tm+1,tr);
    seg[id]=(seg[2*id]+seg[2*id+1])%mod;
}
void pushdown(int id,int tl,int tr){
    if (!marked[id]) return;
    int tm=(tl+tr)/2;
    if (laz[id]%2==1){
        seg[2*id]=(weightps[tm]-weightps[tl-1]+mod-seg[2*id]+mod)%mod;
        seg[2*id+1]=(weightps[tr]-weightps[tm]+mod-seg[2*id+1]+mod)%mod;
    }
    marked[2*id]=1; laz[2*id]+=laz[id];
    marked[2*id+1]=1; laz[2*id+1]+=laz[id];
    marked[id]=0; laz[id]=0;
}
void update(int id,int tl,int tr,int l,int r){
    if (l>r) return;
    if (l<=tl&&tr<=r){
        seg[id]=(weightps[tr]-weightps[tl-1]+mod-seg[id]+mod)%mod;
        laz[id]++;
        marked[id]=1;
        return;
    }
    pushdown(id,tl,tr);
    int tm=(tl+tr)/2;
    update(2*id,tl,tm,l,min(r,tm));
    update(2*id+1,tm+1,tr,max(tm+1,l),r);
    seg[id]=(seg[2*id]+seg[2*id+1])%mod;
}
long long query(int id,int tl,int tr,int l,int r){
    if (l>r) return 0;
    if (l<=tl&&tr<=r) return seg[id];
    pushdown(id,tl,tr);
    int tm=(tl+tr)/2;
    long long lx=query(2*id,tl,tm,l,min(r,tm));
    long long rx=query(2*id+1,tm+1,tr,max(l,tm+1),r);
    return (lx+rx)%mod;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    n=M; dif=N-1;
    for (int i=1; i<N+M; i++) g[P[i]].push_back(i);
    dfs1(0);
    ac[0]=1;
    dfs2(0);
    for (int i=1; i<=n; i++) weight[i]=ac[i+N-1];
    for (int i=1; i<=n; i++) weightps[i]=(weightps[i-1]+weight[i])%mod;
    for (int i=1; i<=n; i++) a[i]=A[i-1];
    build(1,1,n);
}
 
int count_ways(int L, int R) {
    L-=dif; R-=dif;
    update(1,1,n,L,R);
    return query(1,1,n,1,n);
}

Compilation message (stderr)

circuit.cpp: In function 'void dfs1(int)':
circuit.cpp:24:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         for (int i=0; i<g[cur].size(); i++){
      |                       ~^~~~~~~~~~~~~~
circuit.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |             if (i==g[cur].size()-1) ba[i]=sz[g[cur][i]];
      |                 ~^~~~~~~~~~~~~~~~~
circuit.cpp:32:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for (int i=0; i<g[cur].size(); i++){
      |                       ~^~~~~~~~~~~~~~
circuit.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |             if (i+1<g[cur].size()) t=t*ba[i+1]%mod;
      |                 ~~~^~~~~~~~~~~~~~

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