oj.uz

Submission #826086

# Submission time Handle Problem Language Result Execution time Memory
826086 2023-08-15T10:17:28 Z PixelCat Digital Circuit (IOI22_circuit) C++17
16 / 100
 1540 ms 12464 KB 
#include "circuit.h"

#ifdef NYAOWO
#include "stub.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 200'000;
const int MOD = 1'000'002'022;

int n, m;
vector<int> adj[MAXN + 10];
int p[MAXN + 10];
int dp[MAXN + 10][2];
int a[MAXN + 10];
int flip[MAXN + 10];

void update(int x) {
    if(x >= n) {
        dp[x][a[x]] = 1;
        dp[x][1 - a[x]] = 0;
        if(flip[x]) swap(dp[x][0], dp[x][1]);
        return;
    }
    vector<int> v(1, 1);
    for(auto &child:adj[x]) {
        vector<int> v2;
        v2.eb(v[0] * dp[child][0] % MOD);
        For(i, 1, sz(v) - 1) {
            v2.eb((v[i] * dp[child][0] + v[i - 1] * dp[child][1]) % MOD);
        }
        v2.eb(v.back() * dp[child][1] % MOD);
        v.swap(v2);
    }
    dp[x][0] = dp[x][1] = 0;
    int c = sz(adj[x]);
    For(i, 0, c) {
        dp[x][0] = (dp[x][0] + v[i] * (c - i)) % MOD;
        dp[x][1] = (dp[x][1] + v[i] * i) % MOD;
    }
    if(flip[x]) swap(dp[x][0], dp[x][1]);
}

void init(i32 N, i32 M, std::vector<i32> P, std::vector<i32> A) {
    n = N; m = M;
    p[0] = -1;
    For(i, 1, n + m - 1) {
        adj[P[i]].eb(i);
        p[i] = P[i];
    }
    For(i, 0, m - 1) {
        a[n + i] = A[i];
    }
    Forr(i, n + m - 1, 0) update(i);
}

#define L(id) ((id) * 2 + 1)
#define R(id) ((id) * 2 + 2)
void range_flip(int id, int l, int r, int L, int R) {
    if(l >= L && r <= R) {
        flip[id] ^= 1;
        update(id);
        // cerr << id << " " << l << " " << r << " " << dp[id][1] << dp[id][0] << "\n";
        return;
    }
    int mi = (l + r) / 2;
    if(L <= mi) range_flip(L(id), l, mi, L, R);
    if(R > mi)  range_flip(R(id), mi + 1, r, L, R);
    update(id);
}

i32 count_ways(i32 L, i32 R) {
    // int i = L;
    // swap(dp[i][0], dp[i][1]);
    // i = p[i];
    // while(i >= 0) {
    //     update(i);
    //     i = p[i];
    // }
    range_flip(0, n, n + m - 1, L, R);
    return (i32)dp[0][1];
}

/*

3 4 3
-1 0 1 2 1 1 0
1 0 1 0
3 4
4 5
3 6

2
0
6

*/

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5032 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Incorrect 19 ms 5108 KB 1st lines differ - on the 1st token, expected: '509', found: '502'
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 2 ms 5072 KB Output is correct
4 Correct 2 ms 5072 KB Output is correct
5 Correct 2 ms 5072 KB Output is correct
6 Incorrect 3 ms 5072 KB 1st lines differ - on the 1st token, expected: '706880838', found: '445274432'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5032 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Incorrect 19 ms 5108 KB 1st lines differ - on the 1st token, expected: '509', found: '502'
4 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 750 ms 8508 KB Output is correct
2 Correct 1142 ms 12104 KB Output is correct
3 Correct 1218 ms 12156 KB Output is correct
4 Correct 1113 ms 12124 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 750 ms 8508 KB Output is correct
2 Correct 1142 ms 12104 KB Output is correct
3 Correct 1218 ms 12156 KB Output is correct
4 Correct 1113 ms 12124 KB Output is correct
5 Correct 1057 ms 8748 KB Output is correct
6 Correct 1315 ms 12464 KB Output is correct
7 Correct 1387 ms 12464 KB Output is correct
8 Correct 1540 ms 12124 KB Output is correct
9 Correct 525 ms 5200 KB Output is correct
10 Correct 1109 ms 5432 KB Output is correct
11 Correct 1150 ms 5456 KB Output is correct
12 Correct 1200 ms 5456 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 2 ms 5072 KB Output is correct
4 Correct 2 ms 5072 KB Output is correct
5 Correct 2 ms 5072 KB Output is correct
6 Incorrect 3 ms 5072 KB 1st lines differ - on the 1st token, expected: '706880838', found: '445274432'
7 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5032 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Incorrect 19 ms 5108 KB 1st lines differ - on the 1st token, expected: '509', found: '502'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5032 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Incorrect 19 ms 5108 KB 1st lines differ - on the 1st token, expected: '509', found: '502'
4 Halted 0 ms 0 KB -