Submission #720974

#	Time	Username	Problem	Language	Result	Execution time	Memory
720974		lam	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1172 ms	39400 KiB

circuit

#include "circuit.h"

#include <vector>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair<ll,ll> ii;
#define ff first
#define ss second
const int maxn = 2e5 + 10;
const ll mod =  1000002022LL;
int n,m;
int a[maxn];
vector <int> adj[maxn];
ll s[maxn],dp[maxn],sdp[maxn];
void dfs(int x)
{
    s[x] = 1LL;
    if (adj[x].empty()) return;
    for (int i:adj[x])
    {
        dfs(i);
        s[x]=s[x]*s[i]%mod;
    }
    s[x] = s[x]*(ll)adj[x].size()%mod;
}
void dfs2(int x, ll val)
{
//    cerr<<x<<" :: "<<val<<" & "<<s[x]<<endl;
    if (x>=n)
    {
        dp[x-n+1] = val;
        return;
    }
    vector <ll> pre,suf;
    for (int i:adj[x])
    {
        pre.push_back(s[i]);
        suf.push_back(s[i]);
    }
    for (int i=1; i<pre.size(); i++) pre[i]=pre[i]*pre[i-1]%mod;
    for (int i=suf.size()-2; i>=0; i--) suf[i]=suf[i]*suf[i+1]%mod;
    int cnt=0;
//    for (int i:pre) cerr<<i<<' '; cerr<<endl;
//    for (int i:suf) cerr<<i<<' '; cerr<<endl;
//    cerr<<"------------"<<endl;
    for (int i:adj[x])
    {
        ll val2 = val;
        if (cnt>0) val2=val2*pre[cnt-1]%mod;
        if (cnt<suf.size()-1) val2=val2*suf[cnt+1]%mod;
        cnt++;
        dfs2(i,val2);
    }

}
ll f[4*maxn]; bool rev[4*maxn];
void pushrev(int x, int lx, int rx)
{
//    cerr<<"rev "<<lx<<' '<<rx<<endl;
//    cerr<<f[x]<<" ";
    f[x] = (sdp[rx]-sdp[lx-1]+mod-f[x]+mod)%mod;
//    cerr<<"--> "<<f[x]<<endl;
    rev[x]^=1;
}
void down(int x, int lx, int rx)
{
    if (lx==rx) return;
    int mid=(lx+rx)/2;
    if (rev[x])
    {
        pushrev(2*x,lx,mid);
        pushrev(2*x+1,mid+1,rx);
        rev[x]=0;
    }
}
void add(int x, int lx, int rx, int l, int r)
{
    if (lx>r||rx<l) return;
    if (lx>=l&&rx<=r)
    {
        pushrev(x,lx,rx);
        return;
    }
    int mid=(lx+rx)/2;
    down(x,lx,rx);
    add(2*x,lx,mid,l,r);
    add(2*x+1,mid+1,rx,l,r);
    f[x]=(f[2*x]+f[2*x+1])%mod;
}
void build(int x, int lx, int rx)
{
    rev[x]=0;
    if (lx==rx)
    {
        f[x]=0LL;
        if (a[lx]) f[x] = dp[lx];
//        cerr<<lx<<" := "<<f[x]<<endl;
        return;
    }
    int mid=(lx+rx)/2;
    build(2*x,lx,mid); build(2*x+1,mid+1,rx);
    f[x]=(f[2*x]+f[2*x+1])%mod;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    n=N; m=M;
    for (int i=0; i<n+m; i++) adj[i].clear();
    for (int i=1; i<n+m; i++)
    {
        int u=i; int v=P[i];
        adj[v].push_back(u);
    }

    for (int i=n; i<n+m; i++) a[i-n+1]=A[i-n];
    dfs(0); dfs2(0,1LL);
//    for (int i=1; i<=m; i++) cerr<<a[i]<<' '; cerr<<endl;
//    for (int i=1; i<=m; i++) cerr<<dp[i]<<' '; cerr<<endl;
    sdp[0]=0LL;
    for (int i=1; i<=m; i++) sdp[i]=(dp[i]+sdp[i-1])%mod;
    build(1,1,m);
}

int count_ways(int L, int R) {
    L-=n; R-=n;
    L++; R++;
//    cerr<<L<<" - "<<R<<endl;
    add(1,1,m,L,R);
    int ans = (f[1])%mod;
    return ans;
}

Compilation message (stderr)

circuit.cpp: In function 'void dfs2(int, long long int)':
circuit.cpp:42:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int i=1; i<pre.size(); i++) pre[i]=pre[i]*pre[i-1]%mod;
      |                   ~^~~~~~~~~~~
circuit.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         if (cnt<suf.size()-1) val2=val2*suf[cnt+1]%mod;
      |             ~~~^~~~~~~~~~~~~

• 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