Submission #1172931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172931		davele	Digital Circuit (IOI22_circuit)	C++20	18 / 100	3077 ms	8348 KiB

circuit

#ifndef davele
#include "circuit.h"
#endif // davele

#include <bits/stdc++.h>
//#define int long long
#define pii pair<int, int>
#define fi first
#define se second
#define vi vector <int>
#define pq priority_queue
#define MASK(i) (1ll<<(i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define x0 ___x0
#define y0 ___y0
#define div   ___div
#define next   ___next
#define prev   ___prev
#define left   ___left
#define right   ___right
#define pos pisosi
#define pb push_back
#define pf push_front
using namespace std;

const int mod = 1e9+2022;
void add (int &a, const int&b){
    a+=b;
    if (a>=mod) a-=mod;
}

void sub (int&a, const int&b){
    a-=b;
    if (a<0) a+=mod;
}

void mul (int&a, const int&b){
    a = 1ll*a*b%mod;
}

template<class X, class Y>
    bool minimize(X &x, const Y&y){
        if (x<=y) return false;
        else{
            x = y;
            return true;
        }
    }
template<class X, class Y>
    bool maximize (X &x, const Y&y){
        if (x>=y) return false;
        else{
            x = y;
            return true;
        }
    }

////////////////////////////////////////////////////////////////////////////
const int lim = 21e4, limit = lim+5;

int color[limit], tot[limit], numCom[limit], deg[limit];
int numRoot, numLeaf;
vector <int> adj[limit];


#ifdef davele
void init (int N, int M, int P[], int A[]){
#endif // davele

#ifndef davele
void init (int N, int M, std::vector<int> P, std::vector<int> A){
#endif // davele
    numRoot = N;
    numLeaf = M;
    for (int i=1; i<N+M; i++){
        int u = i, v = P[i];
        deg[v]++;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    for (int i=0; i<M; i++){
        int u = N+i;
        color[u] = A[i];
    }
}

void dfs (int u, int pre){
    //
    // tot[u] : so cac bo tham so de dinh u duoc bat
    // dp[i]: so cac bo tham so de co i dinh con duoc bat
    // notmark : so cac bo tham so de dinh v khong duoc bat
    //
    if (u>=numRoot){
        numCom[u] = 1;
        tot[u] = color[u];
        return;
    }
    numCom[u] = deg[u];
    vector <int> dp (deg[u]+2, 0);
    dp[0] = 1;
    int sz = 0;
    for (int v:adj[u]){
        if (v==pre) continue;
        dfs (v, u);
        int notmark = numCom[v] - tot[v];
        if (notmark<0) notmark+=mod;
        mul (numCom[u], numCom[v]);
        for (int i=sz; i>=0; i--){
            dp[i+1] = (1ll*dp[i]*tot[v]%mod + 1ll*dp[i+1]*notmark%mod)%mod;
        }
        mul (dp[0], notmark);
        sz++;
    }
//    cerr<<u<<" "<<numCom[u]<<"\n";
    tot[u] = 0;
    for (int i=1; i<=deg[u]; i++) add(tot[u], 1ll*dp[i]*i%mod);
//    cerr<<u<<"\n";
//    for (int i=1; i<=deg[u]; i++) cerr<<dp[i]<<" ";
//    cerr<<"\n";
}

int count_ways (int L, int R){
    for (int i=L; i<=R; i++) color[i] = 1-color[i];
//    for (int i=numRoot; i<numRoot+numLeaf; i++) cerr<<i<<" "<<color[i]<<"\n";
    dfs(0, 0);
    return tot[0];
}

/*
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    freopen("circuit.inp", "r", stdin);
    freopen("circuit.out", "w", stdout);
    int n, m, q;
    cin>>n>>m>>q;
    int p[n+m+20];
    for (int i=0; i<n+m; i++){
//        cout<<"Root of "<<i<<": "<<endl;
        cin>>p[i];
    }
    //
    int a[m+20];
    for (int i=0; i<m; i++){
//        cout<<"Val of "<<i+n<<": "<<endl;
        cin>>a[i];
    }
    init(n, m, p, a);
    while (q--){
        int L, R;
        cin>>L>>R;

        cout<<count_ways(L, R)<<"\n";
    }
}
*/

• 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: 0 / 28
• Subtask 8: 0 / 11