oj.uz

Submission #680999

# Submission time Handle Problem Language Result Execution time Memory
680999 2023-01-12T08:26:43 Z Ninja_Kunai Digital Circuit (IOI22_circuit) C++17
18 / 100
 3000 ms 7432 KB 
/**
*    Author :  Nguyen Tuan Vu
*    Created : 11.01.2023
**/

#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define MASK(x) ((1ll)<<(x))
#define BIT(x, i) (((x)>>(i))&(1))
#define ALL(v)  (v).begin(), (v).end()
#define REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i)
#define db(val) "["#val" = "<<(val)<<"] "
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)

template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) {return l + rng() % (r - l + 1);}

const int N = 2e5 + 5;
const int Mod = 1e9 + 2022;
int n, m, Sub3, Sub5;
vector <int> par, a, adj[N];

struct Fenwick_Tree {
    vector <int> bit;
    Fenwick_Tree(int _m = 0){
        m = _m;
        bit.resize(m + 7, 0);
    }

    void update(int u, int v, int val) {
        for(; u <= m; u += u & -u) bit[u] += val;
        for(++v; v <= m; v += v & -v) bit[v] -= val;
    }

    int get(int u) {
        int ans = 0;
        for (; u; u -= u & -u) ans += bit[u];
        return ans;
    }
} mybit;

void add(int &x, int k) {
    x += k;
    if (x >= Mod) x -= Mod;
}

namespace sub3 {
    bool check() {
        if (n <= 1000 && m <= 1000) return true;
        return false;
    }

    int dp[N][2], f[2][N];
    void dfs(int u) {
        dp[u][0] = dp[u][1] = 0;
        if (u >= n) dp[u][a[u - n] ^ (mybit.get(u - n + 1) & 1)] = 1;
        for (auto v : adj[u]) dfs(v);
        int sz = adj[u].size();
        FOR(i, 0, sz) f[0][i] = f[1][i] = 0;
        f[1][0] = 1;
        int sum = 0;
        REP(i, sz) {
            int v = adj[u][i];
            FOR(Left, 0, sum) {
                add(f[i & 1][Left], 1ll *  f[(i + 1) & 1][Left] * dp[v][0] % Mod);
                add(f[i & 1][Left + 1], 1ll * f[(i + 1) & 1][Left] * dp[v][1] % Mod);
                f[(i + 1) & 1][Left] = 0;
            }

            //if (u == 2) cout << f[i & 1][0] << ' ' << f[i & 1][1] << '\n';
            sum++;
        }

        //if (u == 2) cout << f[(sz - 1) & 1][0] << ' ' << f[(sz - 1) & 1][1] << '\n';
        FOR(j, 0, sz) {
            add(dp[u][0], 1ll * f[(sz - 1) & 1][j] * (sz - j) % Mod);
            add(dp[u][1], 1ll * f[(sz - 1) & 1][j] * j % Mod);
        }

        //cout << u << ' ' << dp[u][0] << ' ' << dp[u][1] << '\n';
    }

    int solve(int L, int R) {
        mybit.update(L - n + 1, R - n + 1, 1);
        //FOR(i, 1, m) cout << ((mybit.get(i) & 1) ^ a[i - 1]) << " \n"[i == m];
        dfs(0);
        return dp[0][1];
    }
}

void init(int N, int M, vector <int> P, vector <int> A) {
    n = N; m = M;
    par = P; a = A;
    mybit = Fenwick_Tree(m);
    FOR(i, 1, n + m - 1) {
        adj[P[i]].push_back(i);
    }

    if (sub3::check()) Sub3 = 1;
    //cout << Sub3 << '\n';
}

int count_ways(int l, int r) {
    if (Sub3 == 1) return sub3::solve(l, r);
}

/*
==================================================+
INPUT:
--------------------------------------------------|
3 4
-1 0 1 2 1 1 0
1 0 1 0
3
3 4
4 5
3 6

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|
2
0
6
--------------------------------------------------|
==================================================+
*/

Compilation message

circuit.cpp: In function 'int count_ways(int, int)':
circuit.cpp:119:1: warning: control reaches end of non-void function [-Wreturn-type]
  119 | }
      | ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 14 ms 4944 KB Output is correct
4 Correct 15 ms 4944 KB Output is correct
5 Correct 15 ms 4944 KB Output is correct
6 Correct 15 ms 4944 KB Output is correct
7 Correct 15 ms 4944 KB Output is correct
8 Correct 16 ms 4944 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4928 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 3 ms 4944 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 4 ms 4944 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 4 ms 5072 KB Output is correct
8 Correct 4 ms 5072 KB Output is correct
9 Correct 4 ms 5072 KB Output is correct
10 Correct 4 ms 5072 KB Output is correct
11 Correct 4 ms 5180 KB Output is correct
12 Correct 4 ms 5072 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 14 ms 4944 KB Output is correct
4 Correct 15 ms 4944 KB Output is correct
5 Correct 15 ms 4944 KB Output is correct
6 Correct 15 ms 4944 KB Output is correct
7 Correct 15 ms 4944 KB Output is correct
8 Correct 16 ms 4944 KB Output is correct
9 Correct 4 ms 4928 KB Output is correct
10 Correct 3 ms 4944 KB Output is correct
11 Correct 3 ms 4944 KB Output is correct
12 Correct 3 ms 4944 KB Output is correct
13 Correct 4 ms 4944 KB Output is correct
14 Correct 3 ms 5072 KB Output is correct
15 Correct 4 ms 5072 KB Output is correct
16 Correct 4 ms 5072 KB Output is correct
17 Correct 4 ms 5072 KB Output is correct
18 Correct 4 ms 5072 KB Output is correct
19 Correct 4 ms 5180 KB Output is correct
20 Correct 4 ms 5072 KB Output is correct
21 Correct 4 ms 5072 KB Output is correct
22 Correct 4 ms 5072 KB Output is correct
23 Correct 5 ms 4944 KB Output is correct
24 Correct 4 ms 5072 KB Output is correct
25 Correct 4 ms 5072 KB Output is correct
26 Correct 5 ms 4976 KB Output is correct
27 Correct 4 ms 5072 KB Output is correct
28 Correct 4 ms 5072 KB Output is correct
29 Correct 15 ms 4944 KB Output is correct
30 Correct 15 ms 4944 KB Output is correct
31 Correct 4 ms 5072 KB Output is correct
32 Correct 4 ms 5072 KB Output is correct
33 Correct 4 ms 4944 KB Output is correct
34 Correct 4 ms 4944 KB Output is correct
35 Correct 6 ms 4944 KB Output is correct
36 Correct 5 ms 5072 KB Output is correct
37 Correct 17 ms 5200 KB Output is correct
38 Correct 16 ms 5208 KB Output is correct
39 Correct 3 ms 5072 KB Output is correct
40 Correct 4 ms 4944 KB Output is correct
41 Correct 4 ms 4944 KB Output is correct
42 Correct 4 ms 4944 KB Output is correct

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3026 ms 7432 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3026 ms 7432 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4928 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 3 ms 4944 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 4 ms 4944 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 4 ms 5072 KB Output is correct
8 Correct 4 ms 5072 KB Output is correct
9 Correct 4 ms 5072 KB Output is correct
10 Correct 4 ms 5072 KB Output is correct
11 Correct 4 ms 5180 KB Output is correct
12 Correct 4 ms 5072 KB Output is correct
13 Execution timed out 3026 ms 7432 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 14 ms 4944 KB Output is correct
4 Correct 15 ms 4944 KB Output is correct
5 Correct 15 ms 4944 KB Output is correct
6 Correct 15 ms 4944 KB Output is correct
7 Correct 15 ms 4944 KB Output is correct
8 Correct 16 ms 4944 KB Output is correct
9 Correct 4 ms 4928 KB Output is correct
10 Correct 3 ms 4944 KB Output is correct
11 Correct 3 ms 4944 KB Output is correct
12 Correct 3 ms 4944 KB Output is correct
13 Correct 4 ms 4944 KB Output is correct
14 Correct 3 ms 5072 KB Output is correct
15 Correct 4 ms 5072 KB Output is correct
16 Correct 4 ms 5072 KB Output is correct
17 Correct 4 ms 5072 KB Output is correct
18 Correct 4 ms 5072 KB Output is correct
19 Correct 4 ms 5180 KB Output is correct
20 Correct 4 ms 5072 KB Output is correct
21 Correct 4 ms 5072 KB Output is correct
22 Correct 4 ms 5072 KB Output is correct
23 Correct 5 ms 4944 KB Output is correct
24 Correct 4 ms 5072 KB Output is correct
25 Correct 4 ms 5072 KB Output is correct
26 Correct 5 ms 4976 KB Output is correct
27 Correct 4 ms 5072 KB Output is correct
28 Correct 4 ms 5072 KB Output is correct
29 Correct 15 ms 4944 KB Output is correct
30 Correct 15 ms 4944 KB Output is correct
31 Correct 4 ms 5072 KB Output is correct
32 Correct 4 ms 5072 KB Output is correct
33 Correct 4 ms 4944 KB Output is correct
34 Correct 4 ms 4944 KB Output is correct
35 Correct 6 ms 4944 KB Output is correct
36 Correct 5 ms 5072 KB Output is correct
37 Correct 17 ms 5200 KB Output is correct
38 Correct 16 ms 5208 KB Output is correct
39 Correct 3 ms 5072 KB Output is correct
40 Correct 4 ms 4944 KB Output is correct
41 Correct 4 ms 4944 KB Output is correct
42 Correct 4 ms 4944 KB Output is correct
43 Execution timed out 3003 ms 5200 KB Time limit exceeded
44 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 14 ms 4944 KB Output is correct
4 Correct 15 ms 4944 KB Output is correct
5 Correct 15 ms 4944 KB Output is correct
6 Correct 15 ms 4944 KB Output is correct
7 Correct 15 ms 4944 KB Output is correct
8 Correct 16 ms 4944 KB Output is correct
9 Correct 4 ms 4928 KB Output is correct
10 Correct 3 ms 4944 KB Output is correct
11 Correct 3 ms 4944 KB Output is correct
12 Correct 3 ms 4944 KB Output is correct
13 Correct 4 ms 4944 KB Output is correct
14 Correct 3 ms 5072 KB Output is correct
15 Correct 4 ms 5072 KB Output is correct
16 Correct 4 ms 5072 KB Output is correct
17 Correct 4 ms 5072 KB Output is correct
18 Correct 4 ms 5072 KB Output is correct
19 Correct 4 ms 5180 KB Output is correct
20 Correct 4 ms 5072 KB Output is correct
21 Correct 4 ms 5072 KB Output is correct
22 Correct 4 ms 5072 KB Output is correct
23 Correct 5 ms 4944 KB Output is correct
24 Correct 4 ms 5072 KB Output is correct
25 Correct 4 ms 5072 KB Output is correct
26 Correct 5 ms 4976 KB Output is correct
27 Correct 4 ms 5072 KB Output is correct
28 Correct 4 ms 5072 KB Output is correct
29 Correct 15 ms 4944 KB Output is correct
30 Correct 15 ms 4944 KB Output is correct
31 Correct 4 ms 5072 KB Output is correct
32 Correct 4 ms 5072 KB Output is correct
33 Correct 4 ms 4944 KB Output is correct
34 Correct 4 ms 4944 KB Output is correct
35 Correct 6 ms 4944 KB Output is correct
36 Correct 5 ms 5072 KB Output is correct
37 Correct 17 ms 5200 KB Output is correct
38 Correct 16 ms 5208 KB Output is correct
39 Correct 3 ms 5072 KB Output is correct
40 Correct 4 ms 4944 KB Output is correct
41 Correct 4 ms 4944 KB Output is correct
42 Correct 4 ms 4944 KB Output is correct
43 Execution timed out 3026 ms 7432 KB Time limit exceeded
44 Halted 0 ms 0 KB -