Submission #1069004

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069004		beaconmc	Digital Circuit (IOI22_circuit)	C++17	100 / 100	863 ms	61776 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)

const ll maxn = 200005;

basic_string<ll> edges[maxn];
ll sub[maxn];
ll realsub[maxn];
ll par[maxn];
ll prod[maxn];
ll prefs[maxn];
ll pos[maxn];
vector<ll> pref[maxn], suff[maxn];

void dfs(ll a){
    prod[a] = 1;
    for (auto&i : edges[a]){
        dfs(i);

        prod[a] *= prod[i];
        prod[a] %= 1000002022;
        pref[a].push_back(prod[a]);
    }
    reverse(edges[a].begin(), edges[a].end());
    ll temp = 1;
    for (auto&i : edges[a]){

        temp *= prod[i];
        temp %= 1000002022;
        suff[a].push_back(temp);
    }
    reverse(suff[a].begin(), suff[a].end());
    reverse(edges[a].begin(), edges[a].end());
    if ( edges[a].size() != 0) prod[a] *= edges[a].size();
    prod[a] %= 1000002022;
}

ll cache[maxn];

ll dp(ll a){

    if (cache[a] != -1) return cache[a];
    if (a==0) return 1;


    cache[a] = dp(par[a]);

    if (pos[a] != 1) cache[a] *= pref[par[a]][pos[a]-2];
    cache[a] %= 1000002022;
    if (pos[a] != suff[par[a]].size()) cache[a] *= suff[par[a]][pos[a]];
    cache[a] %= 1000002022;


    return cache[a] %= 1000002022;
}
ll states[maxn];
ll vals[maxn];

ll ans = 0;
ll n;

ll tree[maxn*4];
ll lazy[maxn*4];


ll calc(ll k, ll x, ll y){
    if (lazy[k]%2==1){
        return prefs[y] - prefs[x] + vals[x] - tree[k];
    }else{
        return tree[k];
    }
}
void push(ll k, ll x, ll y){

    lazy[k*2] += lazy[k];
    lazy[k*2+1] += lazy[k];

    tree[k] = prefs[y] - prefs[x] + vals[x] - tree[k];

    lazy[k] = 0;
}
void update(ll a, ll b, ll k=1, ll x =0, ll y = n-1){
    if (y<a || b<x) return;
    if (a<=x && y<=b){
        lazy[k]++;
        return;
    }

    push(k,x,y);
    ll mid = (x+y)/2;

    update(a,b,k*2,x,mid);
    update(a,b,k*2+1,mid+1,y);

    tree[k] = calc(k*2,x,mid) + calc(k*2+1, mid+1, y);
}
void sets(ll a, ll b, ll val, ll k=1, ll x =0, ll y = n-1){
    if (y<a || b<x) return;
    if (a<=x && y<=b){
        tree[k] = val;
        return;
    }
    ll mid = (x+y)/2;

    sets(a,b,val,k*2,x,mid);
    sets(a,b,val,k*2+1,mid+1,y);

    tree[k] = calc(k*2,x,mid) + calc(k*2+1, mid+1, y);
}

ll query(ll a, ll b, ll k=1, ll x =0, ll y = n-1){
 
    if (y<a || b<x) return 0;
    if (a<=x && y<=b){

        return calc(k,x,y);
    }
    push(k,x,y);
    ll mid = (x+y)/2;
    return query(a,b,k*2,x,mid) + query(a,b,k*2+1,mid+1,y);
}


void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    n = N+M;
    FOR(i,0,maxn) cache[i] = -1, prefs[i] = 0;
    FOR(i,0,4*maxn) tree[i] = 0, lazy[i] = 0;
    par[0] = -1;
    FOR(i,1,N+M){
        edges[P[i]].push_back(i);
        pos[i] = edges[P[i]].size();
        par[i] = P[i];
    }
    dfs(0);

    FOR(i,0,M){
        vals[N+i] = dp(N+i);
        sets(N+i, N+i, vals[N+i]);
    }


    FOR(i,0,N) prefs[i] = 0;
    FOR(i,N,N+M){
        prefs[i] = prefs[i-1] + vals[i];
    }
    FOR(i,0,M){
        if (A[i] == 0) update(N+i,N+i);
    }

}



int count_ways(int L, int R) {

    update(L, R);
    return (query(0,n-1)[phone])%1000002022;
}

Compilation message (stderr)

circuit.cpp: In function 'll dp(ll)':
circuit.cpp:55:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     if (pos[a] != suff[par[a]].size()) cache[a] *= suff[par[a]][pos[a]];
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• 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