제출 #980225

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
980225		nextgenxing	Digital Circuit (IOI22_circuit)	C++17	100 / 100	734 ms	51652 KiB

circuit

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define F0R(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define F0Rd(i, n) for(int i = (n)-1; i >= 0; i--)
#define FORd(i, a, b) for(int i = (b)-1; i >= (a); i--)
#define ff first 
#define ss second 
const int MAX_N = 2e5+5;
const ll MOD = 1e9+2022;

ll add(ll a, ll b){ return (a+b)%MOD; }
ll sub(ll a, ll b){ return (a-b+MOD)%MOD; }
ll mul(ll a, ll b){ return (a*b)%MOD; }
ll ADD(ll &a, ll b){ return a=add(a, b); }
ll SUB(ll &a, ll b){ return a=sub(a, b); }
ll MUL(ll &a, ll b){ return a=mul(a, b); }

int N, M;
ll tot[MAX_N], w[MAX_N], state[MAX_N], sum[4*MAX_N], seg[4*MAX_N], lazy[4*MAX_N], active[4*MAX_N];
vector<int> adj[MAX_N];

void dfs(int curr){
    if(adj[curr].size()) tot[curr] = adj[curr].size();
    else tot[curr] = 1;
    vector<ll> a(adj[curr].size()), b(adj[curr].size());
    F0R(i, adj[curr].size()){
        dfs(adj[curr][i]);
        if(i) a[i] = mul(tot[adj[curr][i]], a[i-1]);
        else a[i] = tot[adj[curr][i]];
        b[i] = tot[adj[curr][i]];
        MUL(tot[curr], tot[adj[curr][i]]);
    }
    F0Rd(i, adj[curr].size()-1) MUL(b[i], b[i+1]);
    F0R(i, adj[curr].size()){
        ll num = 1;
        if(i) MUL(num, a[i-1]);
        if(i < adj[curr].size()-1) MUL(num, b[i+1]);
        MUL(w[adj[curr][i]], num);
    }
}

void dfs2(int curr){
    for(auto child : adj[curr]){
        MUL(w[child], w[curr]);
        dfs2(child);
    }
}

void build(int idx, int l, int r){
    if(l == r){
        active[idx] = state[l];
        sum[idx] = w[l+N];
        seg[idx] = mul(active[idx], sum[idx]);
        return;
    }
    int m = (l+r)/2;
    build(2*idx, l, m), build(2*idx+1, m+1, r);
    seg[idx] = add(seg[2*idx], seg[2*idx+1]);
    sum[idx] = add(sum[2*idx], sum[2*idx+1]);
}

void prop(int idx, int l, int r){
    if(lazy[idx]){
        seg[idx] = sub(sum[idx], seg[idx]);
        if(l != r){
            lazy[2*idx] ^= lazy[idx];
            lazy[2*idx+1] ^= lazy[idx];
        } else active[idx] ^= 1;
        lazy[idx] = 0;
    }
}

void upd(int ql, int qr, int idx, int l, int r){
    prop(idx, l, r);
    if(ql > r || qr < l) return;
    if(ql <= l && qr >= r){
        lazy[idx] ^= 1;
        prop(idx, l, r);
        return;
    }
    int m = (l+r)/2;
    upd(ql, qr, 2*idx, l, m), upd(ql, qr, 2*idx+1, m+1, r);
    seg[idx] = add(seg[2*idx], seg[2*idx+1]);
}

ll qry(int ql, int qr, int idx, int l, int r){
    prop(idx, l, r);
    if(ql > r || qr < l) return 0;
    if(ql <= l && qr >= r) return seg[idx];
    int m = (l+r)/2;
    return add(qry(ql, qr, 2*idx, l, m), qry(ql, qr, 2*idx+1, m+1, r));
}

void init(int n, int m, vector<int> P, vector<int> A){
    N = n, M = m;
    FOR(i, 1, n+m) adj[P[i]].push_back(i);
    F0R(i, m) state[i] = A[i];
    F0R(i, n+m) w[i] = 1;
    dfs(0), dfs2(0);
    build(1, 0, M-1);
}

int count_ways(int l, int r){
    upd(l-N, r-N, 1, 0, M-1);
    return qry(0, M-1, 1, 0, M-1);
}

// int main() {
//   int N, M, Q;
//   assert(3 == scanf("%d %d %d", &N, &M, &Q));
//   std::vector<int> P(N + M), A(M);
//   for (int i = 0; i < N + M; ++i) {
//     assert(1 == scanf("%d", &P[i]));
//   }
//   for (int j = 0; j < M; ++j) {
//     assert(1 == scanf("%d", &A[j]));
//   }
//   init(N, M, P, A);

//   for (int i = 0; i < Q; ++i) {
//     int L, R;
//     assert(2 == scanf("%d %d", &L, &R));
//     printf("%d\n", count_ways(L, R));
//   }
//   return 0;
// }

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

circuit.cpp: In function 'void dfs(int)':
circuit.cpp:7:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define F0R(i, n) for(int i = 0; i < (n); i++)
      |                                    ^
circuit.cpp:31:5: note: in expansion of macro 'F0R'
   31 |     F0R(i, adj[curr].size()){
      |     ^~~
circuit.cpp:7:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define F0R(i, n) for(int i = 0; i < (n); i++)
      |                                    ^
circuit.cpp:39:5: note: in expansion of macro 'F0R'
   39 |     F0R(i, adj[curr].size()){
      |     ^~~
circuit.cpp:42:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         if(i < adj[curr].size()-1) MUL(num, b[i+1]);
      |            ~~^~~~~~~~~~~~~~~~~~~~

• 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