제출 #745274

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
745274		doowey	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1092 ms	37540 KiB

circuit

#include <bits/stdc++.h>
#include "circuit.h"

using namespace std;

typedef long long ll;

const int N = (int)2e5 + 10;
const int MOD = (int)1e9 + 2022;
vector<int> T[N];
int W[N];
int n, m;

void dfs0(int u){
    if(T[u].empty()) W[u] = 1;
    else{
        W[u] = 1;
        for(auto x : T[u]){
            dfs0(x);
            W[u] = (W[u] * 1ll * W[x]) % MOD;
        }
        W[u] = (W[u] * 1ll * T[u].size()) % MOD;
    }
}

int coeff[N];



void dfs1(int u, int wei){
    if(T[u].empty()){
        coeff[u - n] = wei;
        return;
    }
    vector<int> pre, suff;
    for(auto x : T[u]){
        pre.push_back(W[x]);
        suff.push_back(W[x]);
    }
    for(int i = 1; i < pre.size(); i ++ ){
        pre[i] = (pre[i - 1] * 1ll * pre[i]) % MOD;
    }
    for(int i = (int)suff.size() - 2; i >= 0 ; i -- ){
        suff[i] = (suff[i] * 1ll * suff[i + 1]) % MOD;
    }
    int cf;
    for(int i = 0 ;i < T[u].size(); i ++ ){
        cf = 1;
        if(i) cf = (cf * 1ll * pre[i - 1]) % MOD;
        if(i + 1 < T[u].size()) cf = (cf * 1ll * suff[i + 1]) % MOD;
        dfs1(T[u][i], (wei * 1ll * cf) % MOD);
    }

}

vector<int> A;

struct Node{
    int total;
    int cum;
    int flip;
};

Node tr[N * 4 + 512];

void build(int node, int cl, int cr){
    tr[node].total = 0;
    tr[node].cum = 0;
    tr[node].flip = 0;
    if(cl == cr){
        tr[node].total = coeff[cl];
        if(A[cl]) tr[node].cum = coeff[cl];
        return;
    }
    int mid = (cl + cr) / 2;
    build(node * 2, cl, mid);
    build(node * 2 + 1, mid + 1, cr);
    tr[node].total = (tr[node * 2].total + tr[node * 2 + 1].total) % MOD;
    tr[node].cum = (tr[node * 2].cum + tr[node * 2 + 1].cum) % MOD;
}

void init(int _n, int _m, std::vector<int> P, vector<int> _A) {
    n = _n;
    m = _m;
    A = _A;
    for(int i = 1; i < n + m; i ++ ){
        T[P[i]].push_back(i);
    }
    dfs0(0);
    dfs1(0, 1);
    build(1, 0, m - 1);
}

void push(int node, int cl, int cr){
    if(tr[node].flip){
        tr[node].cum = (tr[node].total - tr[node].cum + MOD) % MOD;
        if(cl != cr){
            tr[node * 2].flip ^= 1;
            tr[node * 2 + 1].flip ^= 1;
        }
        tr[node].flip = 0;
    }
}

void inv(int node, int cl, int cr, int tl, int rr){
    push(node, cl, cr);
    if(cr < tl || cl > rr) return;
    if(cl >= tl && cr <= rr){
        tr[node].flip=1;
        push(node,cl,cr);
        return;
    }
    int mid = (cl + cr) / 2;
    inv(node * 2, cl, mid, tl, rr);
    inv(node * 2 + 1, mid + 1, cr, tl, rr);
    tr[node].cum = (tr[node * 2].cum + tr[node * 2 + 1].cum) % MOD;
}

int count_ways(int li, int ri) {
    inv(1, 0, m - 1, li - n, ri - n);
    return tr[1].cum;
}

컴파일 시 표준 에러 (stderr) 메시지

circuit.cpp: In function 'void dfs1(int, int)':
circuit.cpp:40:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i = 1; i < pre.size(); i ++ ){
      |                    ~~^~~~~~~~~~~~
circuit.cpp:47:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i = 0 ;i < T[u].size(); i ++ ){
      |                    ~~^~~~~~~~~~~~~
circuit.cpp:50:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         if(i + 1 < T[u].size()) cf = (cf * 1ll * suff[i + 1]) % MOD;
      |            ~~~~~~^~~~~~~~~~~~~

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