oj.uz

답안 #705563

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
705563 2023-03-04T16:32:13 Z danikoynov 디지털 회로 (IOI22_circuit) C++17
23 / 100
 3000 ms 17860 KB 
#include "circuit.h"

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

const ll mod = 1000002022;
const int maxn = 2e5 + 10;

int n, m, p[maxn], a[maxn];
vector < int > children[maxn];
ll dp[maxn][2], temp[maxn];

void update_state(int v, bool type)
{
    dp[v][0] = dp[v][1] = 0;

    if (v >= n)
    {
        dp[v][1] = a[v - n];
        dp[v][0] = 1 - dp[v][1];
        return;
    }

    int c = children[v].size();
    for (int i = 0; i <= c; i ++)
        temp[i] = 0;

    temp[0] = 1;

    for (int u : children[v])
    {
        int i = c;
        if (type == false)
            i = 1;
        for (i = c; i >= 0; i --)
        {
            temp[i] = (temp[i] * dp[u][0]) % mod;
            if (i > 0)
                temp[i] = (temp[i] + temp[i - 1] * dp[u][1]) % mod;
        }
    }



    for (int i = 0; i <= c; i ++)
    {
        dp[v][0] = (dp[v][0] + temp[i] * (ll)(c - i)) % mod;
        dp[v][1] = (dp[v][1] + temp[i] * (ll)(i)) % mod;
    }
    ///cout << v << " " << dp[v][0] << " " << dp[v][1] << endl;

}
void solve_state(int v)
{


    for (int u : children[v])
    {
        solve_state(u);
    }

    update_state(v, true);



}

ll pw[maxn], pref[maxn];
ll con[maxn];
int act = 0, logM = 0;
int tree[4 * maxn], lazy[4 * maxn];

void build_tree(int root, int left, int right)
{
    if (left == right)
    {
        tree[root] = (con[left] * a[left]) % mod;
        return;
    }

    int mid = (left + right) / 2;
    build_tree(root * 2, left, mid);
    build_tree(root * 2 + 1, mid + 1, right);

    tree[root] = (tree[root * 2] + tree[root * 2 + 1]) % mod;
}

ll get_sum(int left, int right)
{
    ll sum = pref[right];
    if (left != 0)
        sum = sum - pref[left - 1];
    if (sum < 0)
        sum += mod;
    return sum;
}

void push_lazy(int root, int left, int right)
{
    if (lazy[root] == 0)
        return;

    tree[root] = (get_sum(left, right) - tree[root] + mod) % mod;
    if (left != right)
    {
        lazy[root * 2] = (lazy[root * 2] + 1) % 2;
        lazy[root * 2 + 1] = (lazy[root * 2 + 1] + 1) % 2;
    }
    lazy[root] = 0;
}

void update_range(int root, int left, int right, int qleft, int qright)
{

    push_lazy(root, left, right);
    if (left > qright || right < qleft)
        return;

    if (left >= qleft && right <= qright)
    {
        lazy[root] = 1;
        push_lazy(root, left, right);
        ///cout << left << " :: " << right << " :: " << tree[root] << endl;
        return;
    }

    int mid = (left + right) / 2;
    update_range(root * 2, left, mid, qleft, qright);
    update_range(root * 2 + 1, mid + 1, right, qleft,  qright);
    ///cout << root << " " << left << " " << right << " " << qleft << " " << qright << endl;
    tree[root] = (tree[root * 2] + tree[root * 2 + 1]) % mod;
    ///cout << tree[root] << endl;
}



void init(int N, int M, std::vector<int> P, std::vector<int> A)
{
    n = N;
    m = M;
    for (int i = 0; i < N + M; i ++)
        p[i] = P[i];


    for (int i = 1; i < N + M; i ++)
    {
        children[p[i]].push_back(i);
    }

    solve_state(0);
    for (int i = 0; i < M; i ++)
    {
        a[i] = 1;
        int v = i + n;
        while(v != -1)
        {
            update_state(v, false);
            v = p[v];
        }
        ///solve_state(0);
        con[i] = dp[0][1];
        a[i] = 0;
                 v = i + n;
        while(v != -1)
        {
            update_state(v, false);
            v = p[v];
        }
    }
    pref[0] = con[0];
    for (int i = 1; i < M; i ++)
        pref[i] = (pref[i - 1] + con[i]) % mod;
    for (int i = 0; i < M; i ++)
        a[i] = A[i];


    build_tree(1, 0, m - 1);
}


int count_ways(int L, int R)
{
    update_range(1, 0, m - 1, L - n, R - n);
    ///for (int i = L - n; i <= R - n; i ++)
       /// a[i] = ((a[i] + 1) & 1);

    /**ll ans = 0;
    for (int i = 0; i < m; i ++)
    {

        ans = (ans + (con[i] * a[i])) % mod;
    }*/


    /**cout << "-----------" << endl;
    for (int i = 0; i < n + m; i ++)
        cout << i << " : " << dp[i][0] << " " << dp[i][1] << endl;*/

    return tree[1];
}

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Execution timed out 3064 ms 5072 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 5072 KB Output is correct
3 Correct 3 ms 5072 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 4 ms 5072 KB Output is correct
7 Correct 4 ms 5072 KB Output is correct
8 Correct 5 ms 5072 KB Output is correct
9 Correct 4 ms 5136 KB Output is correct
10 Correct 47 ms 5164 KB Output is correct
11 Correct 45 ms 5164 KB Output is correct
12 Correct 4 ms 5072 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Execution timed out 3064 ms 5072 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 562 ms 8904 KB Output is correct
2 Correct 884 ms 12940 KB Output is correct
3 Correct 748 ms 13000 KB Output is correct
4 Correct 817 ms 12908 KB Output is correct

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 562 ms 8904 KB Output is correct
2 Correct 884 ms 12940 KB Output is correct
3 Correct 748 ms 13000 KB Output is correct
4 Correct 817 ms 12908 KB Output is correct
5 Correct 555 ms 9028 KB Output is correct
6 Correct 639 ms 12956 KB Output is correct
7 Correct 1018 ms 12924 KB Output is correct
8 Correct 776 ms 12936 KB Output is correct
9 Correct 478 ms 5200 KB Output is correct
10 Correct 859 ms 5456 KB Output is correct
11 Correct 844 ms 5456 KB Output is correct
12 Correct 890 ms 5456 KB Output is correct

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 5072 KB Output is correct
3 Correct 3 ms 5072 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 4 ms 5072 KB Output is correct
7 Correct 4 ms 5072 KB Output is correct
8 Correct 5 ms 5072 KB Output is correct
9 Correct 4 ms 5136 KB Output is correct
10 Correct 47 ms 5164 KB Output is correct
11 Correct 45 ms 5164 KB Output is correct
12 Correct 4 ms 5072 KB Output is correct
13 Correct 562 ms 8904 KB Output is correct
14 Correct 884 ms 12940 KB Output is correct
15 Correct 748 ms 13000 KB Output is correct
16 Correct 817 ms 12908 KB Output is correct
17 Correct 555 ms 9028 KB Output is correct
18 Correct 639 ms 12956 KB Output is correct
19 Correct 1018 ms 12924 KB Output is correct
20 Correct 776 ms 12936 KB Output is correct
21 Correct 478 ms 5200 KB Output is correct
22 Correct 859 ms 5456 KB Output is correct
23 Correct 844 ms 5456 KB Output is correct
24 Correct 890 ms 5456 KB Output is correct
25 Correct 1228 ms 17092 KB Output is correct
26 Correct 1341 ms 17352 KB Output is correct
27 Correct 1269 ms 17352 KB Output is correct
28 Correct 1054 ms 17444 KB Output is correct
29 Execution timed out 3032 ms 17860 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Execution timed out 3064 ms 5072 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Execution timed out 3064 ms 5072 KB Time limit exceeded
4 Halted 0 ms 0 KB -