oj.uz

Submission #839147

# Submission time Handle Problem Language Result Execution time Memory
839147 2023-08-28T19:51:28 Z jasmin Digital Circuit (IOI22_circuit) C++17
2 / 100
 734 ms 6992 KB 
#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;

const long long MOD=1e9+2022;
//const int INF = INT_MAX;

vector<vector<int> > adi;
vector<int> par;
vector<int> state;

vector<vector<long long> > pos;

void update_node(int v){

    int s=adi[v].size()+1;
    vector<long long> cnt(s);
    cnt[0] = 1;

    for(auto u: adi[v]){

        for(int i=s-1; i>=0; i--){

            cnt[i] = (cnt[i]*pos[u][0])%MOD;

            if(0<i){
                cnt[i] += (cnt[i-1]*pos[u][1])%MOD;
                cnt[i]%=MOD;
            }
        }
    }

    long long ssum=0;
    pos[v][1]=0;
    for(int i=s-1; i>=1; i--){
        ssum += cnt[i];
        ssum%=MOD;

        pos[v][1] += ssum;
        pos[v][1] %= MOD;
    }

    ssum=cnt[0];
    for(int i=1; i<s; i++){

        pos[v][0] += ssum;
        pos[v][0] %= MOD;

        ssum += cnt[i];
        ssum %= MOD;
    }
}

void init(int n, int m, vector<int> p, vector<int> a) {

    par = p;
    state.assign(n+m, 0);
    for(int i=0; i<m; i++){
        state[n+i] = a[i];
    }

    adi.assign(n, {});
    for(int i=1; i<n+m; i++){

        adi[p[i]].push_back(i);
    }


    pos.assign(n+m, vector<long long> (2, 0));
    for(int i=n; i<n+m; i++){

        pos[i][state[i]] = 1;
    }
    for(int i=n-1; i>=0; i--){
        update_node(i);
    }
}

int count_ways(int L, int R) {
    
    priority_queue<int> pq;
    for(int i=L; i<=R; i++){

        state[i] = 1-state[i];

        pos[i][state[i]] = 1;
        pos[i][1-state[i]] = 0;

        pq.push(par[i]);
    }

    set<int> done;
    while(!pq.empty()){
        int v=pq.top();
        pq.pop();

        if(done.find(v)!=done.end()) continue;
        done.insert(v);

        update_node(v);

        if(par[v]!=-1){
            pq.push(par[v]);
        }
    }

    return pos[0][1];
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 19 ms 336 KB Output is correct
4 Correct 20 ms 380 KB Output is correct
5 Correct 20 ms 336 KB Output is correct
6 Correct 20 ms 336 KB Output is correct
7 Correct 20 ms 336 KB Output is correct
8 Correct 20 ms 464 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '52130940', found: '631923150'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 19 ms 336 KB Output is correct
4 Correct 20 ms 380 KB Output is correct
5 Correct 20 ms 336 KB Output is correct
6 Correct 20 ms 336 KB Output is correct
7 Correct 20 ms 336 KB Output is correct
8 Correct 20 ms 464 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '52130940', found: '631923150'
11 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 734 ms 6992 KB 1st lines differ - on the 1st token, expected: '431985922', found: '853131272'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 734 ms 6992 KB 1st lines differ - on the 1st token, expected: '431985922', found: '853131272'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '52130940', found: '631923150'
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 19 ms 336 KB Output is correct
4 Correct 20 ms 380 KB Output is correct
5 Correct 20 ms 336 KB Output is correct
6 Correct 20 ms 336 KB Output is correct
7 Correct 20 ms 336 KB Output is correct
8 Correct 20 ms 464 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '52130940', found: '631923150'
11 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 19 ms 336 KB Output is correct
4 Correct 20 ms 380 KB Output is correct
5 Correct 20 ms 336 KB Output is correct
6 Correct 20 ms 336 KB Output is correct
7 Correct 20 ms 336 KB Output is correct
8 Correct 20 ms 464 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '52130940', found: '631923150'
11 Halted 0 ms 0 KB -