oj.uz

Submission #835859

# Submission time Handle Problem Language Result Execution time Memory
835859 2023-08-23T21:20:01 Z gagik_2007 Digital Circuit (IOI22_circuit) C++17
16 / 100
 977 ms 12748 KB 
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+2022;
const ll N=200007;
ll n,m,k;
vector<ll>g[N];
vector<ll>p;
vector<ll>a;
ll tot[N];
ll dp[N];
bool lazy[2*N];

void push(int v){
    if(lazy[v]){
        dp[v]=tot[v]-dp[v];
        dp[v]+=MOD;
        dp[v]%=MOD;
        lazy[2*(v+1)-1]=!lazy[2*(v+1)-1];
        lazy[2*(v+1)]=!lazy[2*(v+1)];
        lazy[v]=false;
    }
}

void calc_tot(ll v){
    if(!g[v].size()){tot[v]=1;return;}
    tot[v]=g[v].size();
    for(ll to:g[v]){
        calc_tot(to);
        tot[v]*=tot[to];
        tot[v]%=MOD;
    }
}

void calc_dp(ll v){
    if(!g[v].size()){
        dp[v]=a[v];
        return;
    }
    for(ll to:g[v])calc_dp(to);
    vector<ll>d;
    ll cur=1;
    for(ll to:g[v]){
        d.push_back(cur);
        cur*=tot[to];
        cur%=MOD;
    }
    cur=1;
    ll sum=0;
    // cout<<"DDDDD\n";
    for(ll i=g[v].size()-1;i>=0;i--){
        // cout<<g[v][i]<<": "<<d[i]<<" ";
        d[i]*=cur;
        d[i]%=MOD;
        // cout<<d[i]<<" ";
        d[i]*=dp[g[v][i]];
        d[i]%=MOD;
        // cout<<d[i]<<endl;
        sum+=d[i];
        sum%=MOD;
        cur*=tot[g[v][i]];
        cur%=MOD;
    }
    dp[v]=sum;
}

void just_calc_dp(ll v){
    push(v);
    if(!g[v].size()){
        // dp[v]=a[v];
        return;
    }
    push(2*v);
    push(2*v+1);
}

void update(int v, int tl, int tr, int l, int r){
    push(v-1);
    if(l>r)return;
    if(tl==l&&tr==r){
        // cout<<v-1<<": "<<tl<<" "<<tr<<endl;
        lazy[v-1]=true;
        push(v-1);
    }
    else{
        int tm=(tl+tr)/2;
        update(2*v,tl,tm,l,min(r,tm));
        update(2*v+1,tm+1,tr,max(l,tm+1),r);
        dp[v-1]=dp[2*v-1]*tot[2*v+1-1]+dp[2*v+1-1]*tot[2*v-1];
        dp[v-1]%=MOD;
    }
}

void init(int NN, int MM, vector<int> P, vector<int> A) {
    n=NN;
    m=MM;
    for(ll v=1;v<n+m;v++){
        g[P[v]].push_back(v);
        // g[v].push_back(P[v]);
    }
    for(int x:P)p.push_back(x);
    a.resize(n+m,0);
    for(ll i=0;i<m;i++){
        a[i+n]=A[i];
    }
    calc_tot(0);
    calc_dp(0);
    // for(int v=0;v<n+m;v++){
    //     push(v);
    //     cout<<v<<": "<<dp[v]<<endl;
    // }
    // for(ll v=0;v<n+m;v++){
    //     cout<<v<<": "<<tot[v]<<endl;
    // }
}

int count_ways(int L, int R) {
    // cout<<"______________\n";
    update(1,0,m-1,L-n,R-n);
    // for(int v=0;v<n+m;v++){
    //     push(v);
    //     cout<<v<<": "<<dp[v]<<endl;
    // }
    return dp[0];
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Incorrect 2 ms 5072 KB 1st lines differ - on the 1st token, expected: '509', found: '12'
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 3 ms 5072 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Incorrect 3 ms 5072 KB 1st lines differ - on the 1st token, expected: '706880838', found: '586581592'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Incorrect 2 ms 5072 KB 1st lines differ - on the 1st token, expected: '509', found: '12'
4 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 613 ms 8912 KB Output is correct
2 Correct 807 ms 12744 KB Output is correct
3 Correct 776 ms 12740 KB Output is correct
4 Correct 578 ms 12748 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 613 ms 8912 KB Output is correct
2 Correct 807 ms 12744 KB Output is correct
3 Correct 776 ms 12740 KB Output is correct
4 Correct 578 ms 12748 KB Output is correct
5 Correct 559 ms 8912 KB Output is correct
6 Correct 977 ms 12740 KB Output is correct
7 Correct 682 ms 12748 KB Output is correct
8 Correct 634 ms 12740 KB Output is correct
9 Correct 440 ms 5276 KB Output is correct
10 Correct 804 ms 5552 KB Output is correct
11 Correct 598 ms 5580 KB Output is correct
12 Correct 623 ms 5544 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 3 ms 5072 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Incorrect 3 ms 5072 KB 1st lines differ - on the 1st token, expected: '706880838', found: '586581592'
7 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Incorrect 2 ms 5072 KB 1st lines differ - on the 1st token, expected: '509', found: '12'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Incorrect 2 ms 5072 KB 1st lines differ - on the 1st token, expected: '509', found: '12'
4 Halted 0 ms 0 KB -