oj.uz

Submission #1070267

# Submission time Handle Problem Language Result Execution time Memory
1070267 2024-08-22T12:39:13 Z Unforgettablepl Digital Circuit (IOI22_circuit) C++17
16 / 100
 1056 ms 7864 KB 
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;

const long long modulo = 1e9+2022;

namespace {
    int N,M;
    vector<vector<int>> adj;
    vector<int> A,P;
    vector<pair<long long,long long>> DPtree;
    vector<int> updated;
    vector<bool> switchGreedy;
    int Q;
}

void init(int N,int M,vector<int> P,vector<int> A){
    ::N = N;
    ::M = M;
    ::A = A;
    ::P = P;
    Q = 0;
    switchGreedy = vector<bool>(N+M);
    updated = vector<int>(N+M);
    DPtree = vector<pair<long long,long long>>(N);
    adj = vector<vector<int>>(N);
    for(int i=1;i<N+M;i++)adj[P[i]].emplace_back(i);
    function<pair<long long,long long>(int)> dfs = [&](int x)->pair<long long,long long>{
        if(x>=N) {
            return {A[x-N],1};
        }
        long long tot_ways = adj[x].size();
        vector<long long> DP(adj[x].size()+1);
        DP[0]=1;
        for(int&i:adj[x]) {
            auto temp = dfs(i);
            tot_ways*=temp.second;
            tot_ways%=modulo;
            long long bad_ways = (temp.second-temp.first+modulo)%modulo;
            for(int j=adj[x].size();j>=0;j--) {
                DP[j]*=bad_ways;
                DP[j]%=modulo;
                if(j)DP[j]+=temp.first*DP[j-1];
                DP[j]%=modulo;
            }
        }
        long long ans = 0;
        for(long long i=1;i<=adj[x].size();i++) {
            ans+=DP[i]*i;
            ans%=modulo;
        }
        DPtree[x]={ans,tot_ways};
        return {ans,tot_ways};
    };
    dfs(0);
}

int count_ways(int L,int R){
    Q++;
    function<pair<long long,long long>(int)> dfs = [&](int x)->pair<long long,long long>{
        if(x>=N) {
            if(switchGreedy[x])return {A[x-N]^1,1};
            return {A[x-N],1};
        }
        if(updated[x]<Q) {
            if(switchGreedy[x])return {(DPtree[x].second-DPtree[x].first+modulo)%modulo,DPtree[x].second};
            return DPtree[x];
        }
        long long tot_ways = adj[x].size();
        vector<long long> DP(adj[x].size()+1);
        DP[0]=1;
        for(int&i:adj[x]) {
            auto temp = dfs(i);
            tot_ways*=temp.second;
            tot_ways%=modulo;
            long long bad_ways = (temp.second-temp.first+modulo)%modulo;
            for(int j=adj[x].size();j>=0;j--) {
                DP[j]*=bad_ways;
                DP[j]%=modulo;
                if(j)DP[j]+=temp.first*DP[j-1];
                DP[j]%=modulo;
            }
        }
        long long ans = 0;
        for(long long i=1;i<=adj[x].size();i++) {
            ans+=DP[i]*i;
            ans%=modulo;
        }
        DPtree[x]={ans,tot_ways};
        if(switchGreedy[x])return {(tot_ways-ans+modulo)%modulo,tot_ways};
        return {ans,tot_ways};
    };
    function<void(int)> set_good = [&](int x) {
        switchGreedy[x]=!switchGreedy[x];
        x = P[x];
        while(x>=0) {
            updated[x]=Q;
            x = P[x];
        }
    };
    while(L<=R) {
        if(L%2==0)set_good(L++);
        if(R&1)set_good(R--);
        if(R<L)break;
        L=(L-1)/2;
        R=(R-1)/2;
    }
    return dfs(0).first;
}

Compilation message

circuit.cpp: In lambda function:
circuit.cpp:48:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for(long long i=1;i<=adj[x].size();i++) {
      |                           ~^~~~~~~~~~~~~~~
circuit.cpp: In lambda function:
circuit.cpp:85:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for(long long i=1;i<=adj[x].size();i++) {
      |                           ~^~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 9.0

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

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 4188 KB Output is correct
2 Correct 825 ms 7768 KB Output is correct
3 Correct 879 ms 7768 KB Output is correct
4 Correct 836 ms 7768 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 4188 KB Output is correct
2 Correct 825 ms 7768 KB Output is correct
3 Correct 879 ms 7768 KB Output is correct
4 Correct 836 ms 7768 KB Output is correct
5 Correct 782 ms 4184 KB Output is correct
6 Correct 1056 ms 7864 KB Output is correct
7 Correct 1046 ms 7852 KB Output is correct
8 Correct 1026 ms 7768 KB Output is correct
9 Correct 394 ms 600 KB Output is correct
10 Correct 909 ms 856 KB Output is correct
11 Correct 933 ms 856 KB Output is correct
12 Correct 809 ms 856 KB Output is correct

Subtask #6
0 / 27.0

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

Subtask #7
0 / 28.0

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

Subtask #8
0 / 11.0

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