oj.uz

Submission #820186

# Submission time Handle Problem Language Result Execution time Memory
820186 2023-08-11T00:30:42 Z maeola Digital Circuit (IOI22_circuit) C++17
13 / 100
 3000 ms 9624 KB 
#include "circuit.h"

#include <bits/stdc++.h>

using ll = long long;

using namespace std;

constexpr int mod = 1e9 + 2022;

struct ST
{
        int pool[2];
};

vector<int> adj[200005];
int choices[200005], coef[200005];
ll ans = 0;
int N, M;

void dfs1(int i)
{
        if (i >= N)
                return choices[i] = 1, void();
        choices[i] = adj[i].size();
        for (int j : adj[i])
        {
                dfs1(j);
                choices[i] = 1ll * choices[i] * choices[j] % mod;
        }
}

void dfs2(int i, int x)
{
        if (i >= N)
        {
                coef[i] = x;
                return;
        }
        int n = adj[i].size();
        vector<int> l(n), r(n);
        for (int j = 0; j < n; j++)
        {
                int w = adj[i][j];
                l[j] = r[j] = choices[w];
                if (j)
                        l[j] = 1ll * l[j] * l[j - 1] % mod;
        }
        for (int j = n - 2; j >= 0; j--)
                r[j] = 1ll * r[j] * r[j + 1] % mod;
        for (int j = 0; j < n; j++)
                dfs2(adj[i][j], 1ll * x * (j ? l[j - 1] : 1) *
                                    (j != n - 1 ? r[j + 1] : 1) % mod);
}

int A[100005];

void init(int N_, int M_, vector<int> P, vector<int> A_)
{
        N = N_, M = M_;
        memcpy(A, A_.data(), sizeof(int) * M);
        assert((int)A_.size() == M);
        for (int i = 1; i < N + M; i++)
                adj[P[i]].push_back(i);
        dfs1(0);
        dfs2(0, 1);

        for (int i = 0; i < M; i++)
        {
                ans += A[i] * coef[i + N];
                ans %= mod;
        }
}

int count_ways(int L, int R)
{
        L -= N, R -= N;
        for (int i = L; i <= R; i++)
        {
                if (A[i])
                {
                        A[i] = 0;
                        ans = (ans + mod - coef[i + N]) % mod;
                }
                else
                {
                        A[i] = 1;
                        ans = (ans + coef[i + N]) % mod;
                }
        }
        return ans;
}

Subtask #1
2.0 / 2.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 2 ms 4944 KB Output is correct
4 Correct 2 ms 4944 KB Output is correct
5 Correct 2 ms 4944 KB Output is correct
6 Correct 3 ms 4944 KB Output is correct
7 Correct 2 ms 4944 KB Output is correct
8 Correct 2 ms 4944 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Correct 3 ms 4944 KB Output is correct
11 Correct 3 ms 4944 KB Output is correct
12 Correct 2 ms 4944 KB Output is correct
13 Correct 2 ms 4944 KB Output is correct
14 Correct 2 ms 4944 KB Output is correct
15 Correct 3 ms 5072 KB Output is correct
16 Correct 3 ms 5072 KB Output is correct
17 Correct 2 ms 5072 KB Output is correct
18 Correct 3 ms 5200 KB Output is correct
19 Correct 3 ms 5204 KB Output is correct
20 Correct 2 ms 5072 KB Output is correct
21 Incorrect 2 ms 4944 KB 1st lines differ - on the 1st token, expected: '759476520', found: '705674784'
22 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 7304 KB Output is correct
2 Correct 666 ms 9544 KB Output is correct
3 Correct 564 ms 9608 KB Output is correct
4 Correct 639 ms 9624 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 7304 KB Output is correct
2 Correct 666 ms 9544 KB Output is correct
3 Correct 564 ms 9608 KB Output is correct
4 Correct 639 ms 9624 KB Output is correct
5 Execution timed out 3079 ms 7296 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 3 ms 4944 KB Output is correct
4 Correct 2 ms 4944 KB Output is correct
5 Correct 2 ms 4944 KB Output is correct
6 Correct 2 ms 4944 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 3 ms 5072 KB Output is correct
9 Correct 2 ms 5072 KB Output is correct
10 Correct 3 ms 5200 KB Output is correct
11 Correct 3 ms 5204 KB Output is correct
12 Correct 2 ms 5072 KB Output is correct
13 Correct 333 ms 7304 KB Output is correct
14 Correct 666 ms 9544 KB Output is correct
15 Correct 564 ms 9608 KB Output is correct
16 Correct 639 ms 9624 KB Output is correct
17 Execution timed out 3079 ms 7296 KB Time limit exceeded
18 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 2 ms 4944 KB Output is correct
3 Correct 2 ms 4944 KB Output is correct
4 Correct 2 ms 4944 KB Output is correct
5 Correct 2 ms 4944 KB Output is correct
6 Correct 3 ms 4944 KB Output is correct
7 Correct 2 ms 4944 KB Output is correct
8 Correct 2 ms 4944 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Correct 3 ms 4944 KB Output is correct
11 Correct 3 ms 4944 KB Output is correct
12 Correct 2 ms 4944 KB Output is correct
13 Correct 2 ms 4944 KB Output is correct
14 Correct 2 ms 4944 KB Output is correct
15 Correct 3 ms 5072 KB Output is correct
16 Correct 3 ms 5072 KB Output is correct
17 Correct 2 ms 5072 KB Output is correct
18 Correct 3 ms 5200 KB Output is correct
19 Correct 3 ms 5204 KB Output is correct
20 Correct 2 ms 5072 KB Output is correct
21 Incorrect 2 ms 4944 KB 1st lines differ - on the 1st token, expected: '759476520', found: '705674784'
22 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 2 ms 4944 KB Output is correct
3 Correct 2 ms 4944 KB Output is correct
4 Correct 2 ms 4944 KB Output is correct
5 Correct 2 ms 4944 KB Output is correct
6 Correct 3 ms 4944 KB Output is correct
7 Correct 2 ms 4944 KB Output is correct
8 Correct 2 ms 4944 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Correct 3 ms 4944 KB Output is correct
11 Correct 3 ms 4944 KB Output is correct
12 Correct 2 ms 4944 KB Output is correct
13 Correct 2 ms 4944 KB Output is correct
14 Correct 2 ms 4944 KB Output is correct
15 Correct 3 ms 5072 KB Output is correct
16 Correct 3 ms 5072 KB Output is correct
17 Correct 2 ms 5072 KB Output is correct
18 Correct 3 ms 5200 KB Output is correct
19 Correct 3 ms 5204 KB Output is correct
20 Correct 2 ms 5072 KB Output is correct
21 Incorrect 2 ms 4944 KB 1st lines differ - on the 1st token, expected: '759476520', found: '705674784'
22 Halted 0 ms 0 KB -