oj.uz

Submission #634593

# Submission time Handle Problem Language Result Execution time Memory
634593 2022-08-24T15:25:19 Z JeanBombeur Digital Circuit (IOI22_circuit) C++17
100 / 100
 1137 ms 41288 KB 
#include "circuit.h"
#include <vector>
#include <cstdio>
using namespace std;

//  <|°_°|>

//  Jean Bombeur & M. Broccoli

//  The hardest choices require the strongest wills

//  What is better - to be born good, or to overcome your evil nature with great effort ?

const int MOD = (1000002022);
const int MAX_NODES = (2e5);
const int LOG = (17);
const int SIZE = (1 << LOG);

struct node {
    int val = 0, inv = 0, flag = 0;
};

node operator+(node a, node b) {
    return {a.val + b.val >= MOD ? a.val + b.val - MOD : a.val + b.val, a.inv + b.inv >= MOD ? a.inv + b.inv - MOD : a.inv + b.inv, 0};
}

vector <int> Adj[MAX_NODES];

long long Sz[MAX_NODES];

node Tree[2 * SIZE];

int nbThresholds;

int DfsSz(int node) {
    Sz[node] = Adj[node].size() + Adj[node].empty();
    for (int dest : Adj[node])
        Sz[node] *= DfsSz(dest), Sz[node] %= MOD;
    return Sz[node];
}

void DfsSet(int node, long long value) {
    if (Adj[node].empty())
        Tree[SIZE + node - nbThresholds] = {0, value, 0};
    vector <long long> ProdPref (1, 1);
    vector <long long> ProdSuff (1, 1);
    int sz = Adj[node].size();
    for (int i = 0; i < sz; i ++)
    {
        ProdPref.push_back((ProdPref.back() * Sz[Adj[node][i]]) % MOD);
    }
    for (int i = sz - 1; i >= 0; i --)
    {
        ProdSuff.push_back((ProdSuff.back() * Sz[Adj[node][i]]) % MOD);
    }
    for (int i = 0; i < sz; i ++)
    {
        DfsSet(Adj[node][i], (((value * ProdPref[i]) % MOD) * ProdSuff[sz - i - 1]) % MOD);
    }
    return;
}

void Push(int node) {
    Tree[node].flag = 0;
    swap(Tree[node].val, Tree[node].inv);
    if (node < SIZE)
        Tree[2 * node].flag ^= 1, Tree[2 * node + 1].flag ^= 1;
    return;
}

void Toggle(int node, int qleft, int qright, int left = 0, int right = SIZE) {
    if (Tree[node].flag)
        Push(node);
    if (qright <= left || right <= qleft)
        return;
    if (qleft <= left && right <= qright)
    {
        Push(node);
        return;
    }
    int mid = (left + right) >> 1;
    Toggle(2 * node, qleft, qright, left, mid);
    Toggle(2 * node + 1, qleft, qright, mid, right);
    Tree[node] = Tree[2 * node] + Tree[2 * node + 1];
    return;
}

void init(int nbNodes, int nbSources, vector <int> Parent, vector <int> States) {
    nbThresholds = nbNodes;
    for (int i = 1; i < nbThresholds + nbSources; i ++)
    {
        Adj[Parent[i]].push_back(i);
    }
    DfsSz(0);
    DfsSet(0, 1);
    for (int i = 0; i < nbSources; i ++)
    {
        if (States[i])
            swap(Tree[i + SIZE].val, Tree[i + SIZE].inv);
    }
    for (int i = SIZE - 1; i; i --)
    {
        Tree[i] = Tree[2 * i] + Tree[2 * i + 1];
    }
    return;
}

int count_ways(int left, int right) {
    Toggle(1, left - nbThresholds, (++ right) - nbThresholds);
    return Tree[1].val;
}

Compilation message

circuit.cpp: In function 'void DfsSet(int, long long int)':
circuit.cpp:44:48: warning: narrowing conversion of 'value' from 'long long int' to 'int' [-Wnarrowing]
   44 |         Tree[SIZE + node - nbThresholds] = {0, value, 0};
      |                                                ^~~~~

Subtask #1
2.0 / 2.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6416 KB Output is correct
2 Correct 4 ms 6480 KB Output is correct
3 Correct 4 ms 6480 KB Output is correct
4 Correct 4 ms 6480 KB Output is correct
5 Correct 4 ms 6480 KB Output is correct
6 Correct 5 ms 6480 KB Output is correct
7 Correct 5 ms 6608 KB Output is correct
8 Correct 4 ms 6608 KB Output is correct
9 Correct 5 ms 6608 KB Output is correct
10 Correct 4 ms 6864 KB Output is correct
11 Correct 4 ms 6868 KB Output is correct
12 Correct 5 ms 6540 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6480 KB Output is correct
2 Correct 4 ms 6484 KB Output is correct
3 Correct 6 ms 6580 KB Output is correct
4 Correct 4 ms 6480 KB Output is correct
5 Correct 4 ms 6480 KB Output is correct
6 Correct 4 ms 6480 KB Output is correct
7 Correct 4 ms 6480 KB Output is correct
8 Correct 4 ms 6480 KB Output is correct
9 Correct 4 ms 6416 KB Output is correct
10 Correct 4 ms 6480 KB Output is correct
11 Correct 4 ms 6480 KB Output is correct
12 Correct 4 ms 6480 KB Output is correct
13 Correct 4 ms 6480 KB Output is correct
14 Correct 5 ms 6480 KB Output is correct
15 Correct 5 ms 6608 KB Output is correct
16 Correct 4 ms 6608 KB Output is correct
17 Correct 5 ms 6608 KB Output is correct
18 Correct 4 ms 6864 KB Output is correct
19 Correct 4 ms 6868 KB Output is correct
20 Correct 5 ms 6540 KB Output is correct
21 Correct 5 ms 6480 KB Output is correct
22 Correct 4 ms 6572 KB Output is correct
23 Correct 4 ms 6484 KB Output is correct
24 Correct 5 ms 6616 KB Output is correct
25 Correct 5 ms 6616 KB Output is correct
26 Correct 5 ms 6616 KB Output is correct
27 Correct 5 ms 6616 KB Output is correct
28 Correct 4 ms 6616 KB Output is correct
29 Correct 4 ms 6488 KB Output is correct
30 Correct 4 ms 6560 KB Output is correct
31 Correct 4 ms 6744 KB Output is correct
32 Correct 5 ms 6620 KB Output is correct
33 Correct 4 ms 6488 KB Output is correct
34 Correct 5 ms 6488 KB Output is correct
35 Correct 5 ms 6488 KB Output is correct
36 Correct 4 ms 6872 KB Output is correct
37 Correct 5 ms 6872 KB Output is correct
38 Correct 5 ms 6872 KB Output is correct
39 Correct 4 ms 6616 KB Output is correct
40 Correct 4 ms 6488 KB Output is correct
41 Correct 4 ms 6488 KB Output is correct
42 Correct 4 ms 6488 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 640 ms 9216 KB Output is correct
2 Correct 886 ms 11860 KB Output is correct
3 Correct 889 ms 11848 KB Output is correct
4 Correct 883 ms 11844 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 640 ms 9216 KB Output is correct
2 Correct 886 ms 11860 KB Output is correct
3 Correct 889 ms 11848 KB Output is correct
4 Correct 883 ms 11844 KB Output is correct
5 Correct 839 ms 9228 KB Output is correct
6 Correct 940 ms 11892 KB Output is correct
7 Correct 934 ms 11924 KB Output is correct
8 Correct 722 ms 11816 KB Output is correct
9 Correct 460 ms 6608 KB Output is correct
10 Correct 876 ms 6864 KB Output is correct
11 Correct 784 ms 6864 KB Output is correct
12 Correct 837 ms 6864 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6416 KB Output is correct
2 Correct 4 ms 6480 KB Output is correct
3 Correct 4 ms 6480 KB Output is correct
4 Correct 4 ms 6480 KB Output is correct
5 Correct 4 ms 6480 KB Output is correct
6 Correct 5 ms 6480 KB Output is correct
7 Correct 5 ms 6608 KB Output is correct
8 Correct 4 ms 6608 KB Output is correct
9 Correct 5 ms 6608 KB Output is correct
10 Correct 4 ms 6864 KB Output is correct
11 Correct 4 ms 6868 KB Output is correct
12 Correct 5 ms 6540 KB Output is correct
13 Correct 640 ms 9216 KB Output is correct
14 Correct 886 ms 11860 KB Output is correct
15 Correct 889 ms 11848 KB Output is correct
16 Correct 883 ms 11844 KB Output is correct
17 Correct 839 ms 9228 KB Output is correct
18 Correct 940 ms 11892 KB Output is correct
19 Correct 934 ms 11924 KB Output is correct
20 Correct 722 ms 11816 KB Output is correct
21 Correct 460 ms 6608 KB Output is correct
22 Correct 876 ms 6864 KB Output is correct
23 Correct 784 ms 6864 KB Output is correct
24 Correct 837 ms 6864 KB Output is correct
25 Correct 944 ms 14592 KB Output is correct
26 Correct 1044 ms 14624 KB Output is correct
27 Correct 969 ms 14712 KB Output is correct
28 Correct 923 ms 14712 KB Output is correct
29 Correct 957 ms 41272 KB Output is correct
30 Correct 654 ms 41288 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6480 KB Output is correct
2 Correct 4 ms 6484 KB Output is correct
3 Correct 6 ms 6580 KB Output is correct
4 Correct 4 ms 6480 KB Output is correct
5 Correct 4 ms 6480 KB Output is correct
6 Correct 4 ms 6480 KB Output is correct
7 Correct 4 ms 6480 KB Output is correct
8 Correct 4 ms 6480 KB Output is correct
9 Correct 4 ms 6416 KB Output is correct
10 Correct 4 ms 6480 KB Output is correct
11 Correct 4 ms 6480 KB Output is correct
12 Correct 4 ms 6480 KB Output is correct
13 Correct 4 ms 6480 KB Output is correct
14 Correct 5 ms 6480 KB Output is correct
15 Correct 5 ms 6608 KB Output is correct
16 Correct 4 ms 6608 KB Output is correct
17 Correct 5 ms 6608 KB Output is correct
18 Correct 4 ms 6864 KB Output is correct
19 Correct 4 ms 6868 KB Output is correct
20 Correct 5 ms 6540 KB Output is correct
21 Correct 5 ms 6480 KB Output is correct
22 Correct 4 ms 6572 KB Output is correct
23 Correct 4 ms 6484 KB Output is correct
24 Correct 5 ms 6616 KB Output is correct
25 Correct 5 ms 6616 KB Output is correct
26 Correct 5 ms 6616 KB Output is correct
27 Correct 5 ms 6616 KB Output is correct
28 Correct 4 ms 6616 KB Output is correct
29 Correct 4 ms 6488 KB Output is correct
30 Correct 4 ms 6560 KB Output is correct
31 Correct 4 ms 6744 KB Output is correct
32 Correct 5 ms 6620 KB Output is correct
33 Correct 4 ms 6488 KB Output is correct
34 Correct 5 ms 6488 KB Output is correct
35 Correct 5 ms 6488 KB Output is correct
36 Correct 4 ms 6872 KB Output is correct
37 Correct 5 ms 6872 KB Output is correct
38 Correct 5 ms 6872 KB Output is correct
39 Correct 4 ms 6616 KB Output is correct
40 Correct 4 ms 6488 KB Output is correct
41 Correct 4 ms 6488 KB Output is correct
42 Correct 4 ms 6488 KB Output is correct
43 Correct 728 ms 6736 KB Output is correct
44 Correct 933 ms 6736 KB Output is correct
45 Correct 954 ms 6736 KB Output is correct
46 Correct 755 ms 6864 KB Output is correct
47 Correct 805 ms 6912 KB Output is correct
48 Correct 559 ms 6864 KB Output is correct
49 Correct 858 ms 6864 KB Output is correct
50 Correct 942 ms 6864 KB Output is correct
51 Correct 769 ms 6844 KB Output is correct
52 Correct 688 ms 6960 KB Output is correct
53 Correct 810 ms 7888 KB Output is correct
54 Correct 894 ms 6864 KB Output is correct
55 Correct 917 ms 6736 KB Output is correct
56 Correct 663 ms 6736 KB Output is correct
57 Correct 822 ms 6736 KB Output is correct
58 Correct 839 ms 8272 KB Output is correct
59 Correct 910 ms 8152 KB Output is correct
60 Correct 843 ms 8232 KB Output is correct
61 Correct 619 ms 6992 KB Output is correct
62 Correct 946 ms 6736 KB Output is correct
63 Correct 852 ms 6736 KB Output is correct
64 Correct 918 ms 6736 KB Output is correct
65 Correct 455 ms 6608 KB Output is correct
66 Correct 773 ms 6864 KB Output is correct
67 Correct 903 ms 6864 KB Output is correct
68 Correct 724 ms 6864 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6480 KB Output is correct
2 Correct 4 ms 6484 KB Output is correct
3 Correct 6 ms 6580 KB Output is correct
4 Correct 4 ms 6480 KB Output is correct
5 Correct 4 ms 6480 KB Output is correct
6 Correct 4 ms 6480 KB Output is correct
7 Correct 4 ms 6480 KB Output is correct
8 Correct 4 ms 6480 KB Output is correct
9 Correct 4 ms 6416 KB Output is correct
10 Correct 4 ms 6480 KB Output is correct
11 Correct 4 ms 6480 KB Output is correct
12 Correct 4 ms 6480 KB Output is correct
13 Correct 4 ms 6480 KB Output is correct
14 Correct 5 ms 6480 KB Output is correct
15 Correct 5 ms 6608 KB Output is correct
16 Correct 4 ms 6608 KB Output is correct
17 Correct 5 ms 6608 KB Output is correct
18 Correct 4 ms 6864 KB Output is correct
19 Correct 4 ms 6868 KB Output is correct
20 Correct 5 ms 6540 KB Output is correct
21 Correct 5 ms 6480 KB Output is correct
22 Correct 4 ms 6572 KB Output is correct
23 Correct 4 ms 6484 KB Output is correct
24 Correct 5 ms 6616 KB Output is correct
25 Correct 5 ms 6616 KB Output is correct
26 Correct 5 ms 6616 KB Output is correct
27 Correct 5 ms 6616 KB Output is correct
28 Correct 4 ms 6616 KB Output is correct
29 Correct 4 ms 6488 KB Output is correct
30 Correct 4 ms 6560 KB Output is correct
31 Correct 4 ms 6744 KB Output is correct
32 Correct 5 ms 6620 KB Output is correct
33 Correct 4 ms 6488 KB Output is correct
34 Correct 5 ms 6488 KB Output is correct
35 Correct 5 ms 6488 KB Output is correct
36 Correct 4 ms 6872 KB Output is correct
37 Correct 5 ms 6872 KB Output is correct
38 Correct 5 ms 6872 KB Output is correct
39 Correct 4 ms 6616 KB Output is correct
40 Correct 4 ms 6488 KB Output is correct
41 Correct 4 ms 6488 KB Output is correct
42 Correct 4 ms 6488 KB Output is correct
43 Correct 640 ms 9216 KB Output is correct
44 Correct 886 ms 11860 KB Output is correct
45 Correct 889 ms 11848 KB Output is correct
46 Correct 883 ms 11844 KB Output is correct
47 Correct 839 ms 9228 KB Output is correct
48 Correct 940 ms 11892 KB Output is correct
49 Correct 934 ms 11924 KB Output is correct
50 Correct 722 ms 11816 KB Output is correct
51 Correct 460 ms 6608 KB Output is correct
52 Correct 876 ms 6864 KB Output is correct
53 Correct 784 ms 6864 KB Output is correct
54 Correct 837 ms 6864 KB Output is correct
55 Correct 944 ms 14592 KB Output is correct
56 Correct 1044 ms 14624 KB Output is correct
57 Correct 969 ms 14712 KB Output is correct
58 Correct 923 ms 14712 KB Output is correct
59 Correct 957 ms 41272 KB Output is correct
60 Correct 654 ms 41288 KB Output is correct
61 Correct 728 ms 6736 KB Output is correct
62 Correct 933 ms 6736 KB Output is correct
63 Correct 954 ms 6736 KB Output is correct
64 Correct 755 ms 6864 KB Output is correct
65 Correct 805 ms 6912 KB Output is correct
66 Correct 559 ms 6864 KB Output is correct
67 Correct 858 ms 6864 KB Output is correct
68 Correct 942 ms 6864 KB Output is correct
69 Correct 769 ms 6844 KB Output is correct
70 Correct 688 ms 6960 KB Output is correct
71 Correct 810 ms 7888 KB Output is correct
72 Correct 894 ms 6864 KB Output is correct
73 Correct 917 ms 6736 KB Output is correct
74 Correct 663 ms 6736 KB Output is correct
75 Correct 822 ms 6736 KB Output is correct
76 Correct 839 ms 8272 KB Output is correct
77 Correct 910 ms 8152 KB Output is correct
78 Correct 843 ms 8232 KB Output is correct
79 Correct 619 ms 6992 KB Output is correct
80 Correct 946 ms 6736 KB Output is correct
81 Correct 852 ms 6736 KB Output is correct
82 Correct 918 ms 6736 KB Output is correct
83 Correct 455 ms 6608 KB Output is correct
84 Correct 773 ms 6864 KB Output is correct
85 Correct 903 ms 6864 KB Output is correct
86 Correct 724 ms 6864 KB Output is correct
87 Correct 4 ms 6480 KB Output is correct
88 Correct 474 ms 13864 KB Output is correct
89 Correct 964 ms 11888 KB Output is correct
90 Correct 1035 ms 11640 KB Output is correct
91 Correct 807 ms 14740 KB Output is correct
92 Correct 847 ms 14840 KB Output is correct
93 Correct 1137 ms 14748 KB Output is correct
94 Correct 959 ms 14744 KB Output is correct
95 Correct 896 ms 14832 KB Output is correct
96 Correct 697 ms 10564 KB Output is correct
97 Correct 938 ms 10520 KB Output is correct
98 Correct 792 ms 34680 KB Output is correct
99 Correct 892 ms 14848 KB Output is correct
100 Correct 971 ms 12364 KB Output is correct
101 Correct 722 ms 11676 KB Output is correct
102 Correct 989 ms 10484 KB Output is correct
103 Correct 764 ms 41288 KB Output is correct
104 Correct 1004 ms 38748 KB Output is correct
105 Correct 893 ms 38752 KB Output is correct
106 Correct 896 ms 17144 KB Output is correct
107 Correct 1027 ms 10824 KB Output is correct
108 Correct 723 ms 10712 KB Output is correct
109 Correct 917 ms 10620 KB Output is correct