Submission #1167495

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167495		SmuggingSpun	Digital Circuit (IOI22_circuit)	C++20	46 / 100	1458 ms	7304 KiB

circuit

#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;
const int lim = 2e5 + 5;
const int mod =  1000002022;
void add(int& a, int b){
    if((a += b) >= mod){
        a -= mod;
    }
}
void sub(int& a, int b){
    if((a -= b) < 0){
        a += mod;
    }
}
int n, m, parent[lim], a[lim];
vector<int>g[lim];
namespace sub1237{
    const int lim = 1e4 + 5;
    int ans = 0, f[lim], coef[lim];
    bitset<lim>vis;
    void init(){
        for(int i = n; i < n + m; i++){
            vector<int>path;
            int u = i;
            vis.reset();
            while(u != -1){
                vis.set(u);
                u = parent[u];
            }
            f[i] = 1;
            for(int j = 0; j < n; j++){
                if(!vis.test(j)){
                    f[i] = 1LL * f[i] * g[j].size() % mod;
                }
            }
            if(a[i] == 1){
                add(ans, f[i]);
            }
        }
    }
    int query(int L, int R){
        for(int i = L; i <= R; i++){
            if((a[i] ^= 1) == 0){
                sub(ans, f[i]);
            }
            else{
                add(ans, f[i]);
            }
        }
        return ans;
    }
}
namespace sub8{
    void init(){

    }
    int query(int L, int R){
        
    }
}
void init(int N, int M, vector<int>P, vector<int>A){
    n = N;
    m = M;
    parent[0] = -1;
    for(int i = 1; i < n + m; i++){
        g[parent[i] = P[i]].emplace_back(i);
    }
    for(int i = 0; i < m; i++){
        a[i + n] = A[i];
    }
    if(max(n, m) <= 5000){
        sub1237::init();
    }
    else{
        sub8::init();
    }
}
int count_ways(int L, int R){
    if(max(n, m) <= 5000){
        return sub1237::query(L, R);
    }
    return sub8::query(L, R);
}

Compilation message (stderr)

circuit.cpp: In function 'int sub8::query(int, int)':
circuit.cpp:60:5: warning: no return statement in function returning non-void [-Wreturn-type]
   60 |     }
      |     ^

• Subtask 1: 2 / 2
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 0 / 4
• Subtask 5: 0 / 12
• Subtask 6: 0 / 27
• Subtask 7: 28 / 28
• Subtask 8: 0 / 11