제출 #1194026

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194026		Ludissey	Digital Circuit (IOI22_circuit)	C++17	46 / 100	3048 ms	5660 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define int long long
using namespace std;

int N,M;
const int MOD=1e9+2022;
vector<vector<int>> child;
vector<int> p;
vector<int> aP;
vector<int> apR;
vector<int> a;

int setup_ap(int x){
    if(x>=N) return aP[x]=1;
    aP[x]=1;
    for (auto u : child[x]) aP[x]=(aP[x]*setup_ap(u))%MOD;
    aP[x]=(aP[x]*sz(child[x]))%MOD;
    return (aP[x])%MOD;
}

void setup_apr(int x, int c){
    vector<int> rgt(sz(child[x])+1,1);
    for (int j=sz(child[x])-1; j>=0; j--) {
        rgt[j]=(rgt[j+1]*aP[child[x][j]])%MOD;
    }
    int mP=1;
    apR[x]=c;
    for (int j=0; j<sz(child[x]); j++) {
        int u=child[x][j];
        int v=(rgt[j+1]*mP)%MOD;
        setup_apr(u,(c*v)%MOD);
        mP=(mP*aP[u])%MOD;
    }
    return;
}


void init(signed n, signed m, std::vector<signed> P, std::vector<signed> A) {
    N=n; M=m;
    p.resize(N+M);
    aP.resize(N+M);
    apR.resize(N+M);
    for (int i = 0; i < N+M; i++) p[i]=P[i];
    child.resize(N+M); a.resize(N+M);
    for (int i = 1; i < N+M; i++) child[P[i]].push_back(i);
    for (int i = N; i < N+M; i++) a[i] = A[i-N];
    setup_ap(0);
    setup_apr(0,1);
}

signed count_ways(signed L, signed R) {
    for (int i = L; i <= R; i++) a[i] = 1-a[i];
    int sum=0;
    for (int i = N; i < N+M; i++) {
        sum=(sum+a[i]*apR[i])%MOD;
    }
    return (int)(sum);
}

• 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