oj.uz

Submission #811014

# Submission time Handle Problem Language Result Execution time Memory
811014 2023-08-06T20:13:14 Z BT21tata Digital Circuit (IOI22_circuit) C++17
18 / 100
 865 ms 15680 KB 
#include "circuit.h"
typedef long long ll;
#include <bits/stdc++.h>
using namespace std;
const ll MOD=1e9+2022;
const int N=2e5+5;

struct tree
{
    ll one, zero, lazy;
}t[4*N];

int nw[N], cnt, old[N], n, m;
ll suff[N], prv=1, a[N];
vector<int>g[N];

void dfs(int v)
{
    if(!g[v].size()) return;
    old[cnt]=v;
    nw[v]=cnt++;
    for(int u : g[v])
        dfs(u);
}

void calc(int v, int p)
{
    if(!g[v].size())
    {
        a[v-n]=prv*suff[nw[p]+1];
        a[v-n]%=MOD;
        //cout<<v<<' '<<p<<' '<<a[v-n]<<' '<<prv<<' '<<suff[nw[p]+1]<<' '<<nw[p]<<endl;
        return;
    }
    
    for(int u : g[v])
        calc(u, v);
    
    prv*=g[v].size();
    prv%=MOD;
}

void build(int v, int l, int r, vector<int>&state)
{
    if(l==r)
    {
        if(state[l]) t[v]={a[l], 0, 0};
        else t[v]={0, a[l], 0};
        return;
    }
    
    int mid=(l+r)>>1;
    build(v<<1, l, mid, state);
    build(v<<1|1, mid+1, r, state);

    t[v]={(t[v<<1].one+t[v<<1|1].one)%MOD, (t[v<<1].zero+t[v<<1|1].zero)%MOD, 0};
}

void push(int v, int l, int r)
{
    swap(t[v].zero, t[v].one);
    t[v].lazy=0;
    t[v<<1].lazy^=1;
    t[v<<1|1].lazy^=1;
}

void update(int v, int l, int r, int tl, int tr)
{
    if(t[v].lazy) push(v, l, r);
    if(r<tl or tr<l) return;
    if(tl<=l and r<=tr)
    {
        t[v].lazy=1;
        push(v, l, r);
        return;
    }

    int mid=(l+r)>>1;
    update(v<<1, l, mid, tl, tr);
    update(v<<1|1, mid+1, r, tl, tr);

    t[v]={(t[v<<1].one+t[v<<1|1].one)%MOD, (t[v<<1].zero+t[v<<1|1].zero)%MOD, 0};
}

void init(int N, int M, vector<int> p, vector<int> state)
{
    n=N; m=M;
    for(int i=1; i<n+m; i++)
        g[p[i]].push_back(i);

    dfs(0);

    suff[n]=1;
    for(int i=n-1; i>=0; i--)
    {
        suff[i]=suff[i+1]*g[old[i]].size();
        suff[i]%=MOD;
    }

    calc(0, -1);

    build(1, 0, m-1, state);
}

int count_ways(int l, int r)
{
    update(1, 0, m-1, l-n, r-n);
    return t[1].one;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 2 ms 5072 KB Output is correct
4 Correct 2 ms 5072 KB Output is correct
5 Correct 2 ms 5116 KB Output is correct
6 Correct 2 ms 5072 KB Output is correct
7 Correct 2 ms 5116 KB Output is correct
8 Correct 2 ms 5112 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 2 ms 5072 KB Output is correct
4 Correct 2 ms 5072 KB Output is correct
5 Correct 2 ms 5116 KB Output is correct
6 Correct 2 ms 5072 KB Output is correct
7 Correct 2 ms 5116 KB Output is correct
8 Correct 2 ms 5112 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Correct 2 ms 5056 KB Output is correct
11 Correct 2 ms 5072 KB Output is correct
12 Correct 2 ms 5072 KB Output is correct
13 Correct 2 ms 5020 KB Output is correct
14 Incorrect 2 ms 5072 KB 1st lines differ - on the 1st token, expected: '706880838', found: '642305882'
15 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 10308 KB Output is correct
2 Correct 761 ms 15640 KB Output is correct
3 Correct 689 ms 15552 KB Output is correct
4 Correct 662 ms 15680 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 10308 KB Output is correct
2 Correct 761 ms 15640 KB Output is correct
3 Correct 689 ms 15552 KB Output is correct
4 Correct 662 ms 15680 KB Output is correct
5 Correct 633 ms 10288 KB Output is correct
6 Correct 770 ms 15580 KB Output is correct
7 Correct 849 ms 15548 KB Output is correct
8 Correct 865 ms 13196 KB Output is correct
9 Correct 339 ms 5328 KB Output is correct
10 Correct 647 ms 5712 KB Output is correct
11 Correct 759 ms 5712 KB Output is correct
12 Correct 673 ms 5456 KB Output is correct

Subtask #6
0 / 27.0

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

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 2 ms 5072 KB Output is correct
4 Correct 2 ms 5072 KB Output is correct
5 Correct 2 ms 5116 KB Output is correct
6 Correct 2 ms 5072 KB Output is correct
7 Correct 2 ms 5116 KB Output is correct
8 Correct 2 ms 5112 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Correct 2 ms 5056 KB Output is correct
11 Correct 2 ms 5072 KB Output is correct
12 Correct 2 ms 5072 KB Output is correct
13 Correct 2 ms 5020 KB Output is correct
14 Incorrect 2 ms 5072 KB 1st lines differ - on the 1st token, expected: '706880838', found: '642305882'
15 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 2 ms 5072 KB Output is correct
4 Correct 2 ms 5072 KB Output is correct
5 Correct 2 ms 5116 KB Output is correct
6 Correct 2 ms 5072 KB Output is correct
7 Correct 2 ms 5116 KB Output is correct
8 Correct 2 ms 5112 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Correct 2 ms 5056 KB Output is correct
11 Correct 2 ms 5072 KB Output is correct
12 Correct 2 ms 5072 KB Output is correct
13 Correct 2 ms 5020 KB Output is correct
14 Incorrect 2 ms 5072 KB 1st lines differ - on the 1st token, expected: '706880838', found: '642305882'
15 Halted 0 ms 0 KB -