oj.uz

Submission #628028

# Submission time Handle Problem Language Result Execution time Memory
628028 2022-08-13T03:34:46 Z Hanksburger Digital Circuit (IOI22_circuit) C++17
100 / 100
 1275 ms 35568 KB 
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
const long long mod=1e9+2022;
long long seg[800005], sum[800005], lazy[800005], state[200005], dp[200005], a[200005], n, m;
vector<long long> adj[200005];
void dfs(long long u)
{
    if (u>=n)
    {
        dp[u]=1;
        return;
    }
    dp[u]=adj[u].size();
    for (long long v:adj[u])
    {
        dfs(v);
        dp[u]=(dp[u]*dp[v])%mod;
    }
}
void dfs2(long long u, long long x)
{
    if (u>=n)
    {
        a[u]=x;
        return;
    }
    vector<long long> vec;
    long long sq=sqrt(adj[u].size());
    for (long long i=0; i<adj[u].size(); i++)
    {
        long long v=adj[u][i];
        if (i%sq==0)
            vec.push_back(dp[v]);
        else
            vec[vec.size()-1]=(vec[vec.size()-1]*dp[v])%mod;
    }
//    cout << "vec: ";
//    for (long long i=0; i<vec.size(); i++)
//        cout << vec[i] << ' ';
//    cout << '\n';
    for (long long i=0; i<adj[u].size(); i++)
    {
        long long v=adj[u][i], y=x;
        for (long long j=0; j<i/sq; j++)
            y=(y*vec[j])%mod;
        for (long long j=i/sq+1; j<vec.size(); j++)
            y=(y*vec[j])%mod;
        for (long long j=i/sq*sq; j<i; j++)
            y=(y*dp[adj[u][j]])%mod;
        for (long long j=i+1; j<min((long long)adj[u].size(), (i/sq+1)*sq); j++)
            y=(y*dp[adj[u][j]])%mod;
        dfs2(v, y);
    }
}
void push(long long i, long long l, long long r)
{
    if (lazy[i])
    {
        seg[i]=(sum[i]-seg[i]+mod)%mod;
        lazy[i]=0;
        lazy[i*2]^=1;
        lazy[i*2+1]^=1;
    }
}
void build(long long i, long long l, long long r)
{
    if (l==r)
    {
        sum[i]=a[l];
        seg[i]=a[l]*state[l];
//        cout << "l r seg " << l << ' ' << r << ' ' << seg[i] << '\n';
        return;
    }
    long long mid=(l+r)/2;
    build(i*2, l, mid);
    build(i*2+1, mid+1, r);
    sum[i]=(sum[i*2]+sum[i*2+1])%mod;
    seg[i]=(seg[i*2]+seg[i*2+1])%mod;
//    cout << "l r seg " << l << ' ' << r << ' ' << seg[i] << '\n';
}
void update(long long i, long long l, long long r, long long ql, long long qr)
{
    push(i, l, r);
    if (ql<=l && r<=qr)
    {
        lazy[i]=1;
        push(i, l, r);
//        cout << "l r seg " << l << ' ' << r << ' ' << seg[i] << '\n';
        return;
    }
    long long mid=(l+r)/2;
    push(i*2, l, mid);
    push(i*2+1, mid+1, r);
    if (l<=qr && ql<=mid)
        update(i*2, l, mid, ql, qr);
    if (mid+1<=qr && ql<=r)
        update(i*2+1, mid+1, r, ql, qr);
    seg[i]=(seg[i*2]+seg[i*2+1])%mod;
//    cout << "l r seg " << l << ' ' << r << ' ' << seg[i] << '\n';
}
void init(int N, int M, vector<int> P, vector<int> A)
{
    n=N;
    m=M;
    for (long long i=1; i<n+m; i++)
        adj[P[i]].push_back(i);
    dfs(0);
    dfs2(0, 1);
//    cout << "a: ";
//    for (long long i=0; i<m; i++)
//        cout << a[i+n] << ' ';
//    cout << '\n';
    for (long long i=0; i<m; i++)
        state[i+n]=A[i];
    build(1, n, n+m-1);
}
int count_ways(int L, int R)
{
    update(1, n, n+m-1, L, R);
    return seg[1];
}

Compilation message

circuit.cpp: In function 'void dfs2(long long int, long long int)':
circuit.cpp:30:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (long long i=0; i<adj[u].size(); i++)
      |                         ~^~~~~~~~~~~~~~
circuit.cpp:42:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (long long i=0; i<adj[u].size(); i++)
      |                         ~^~~~~~~~~~~~~~
circuit.cpp:47:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for (long long j=i/sq+1; j<vec.size(); j++)
      |                                  ~^~~~~~~~~~~

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 4 ms 5056 KB Output is correct
4 Correct 4 ms 5072 KB Output is correct
5 Correct 5 ms 5072 KB Output is correct
6 Correct 5 ms 5140 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 4 ms 5072 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 4 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 3 ms 5072 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 4 ms 5072 KB Output is correct
9 Correct 3 ms 5072 KB Output is correct
10 Correct 5 ms 5200 KB Output is correct
11 Correct 4 ms 5200 KB Output is correct
12 Correct 4 ms 5172 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 4 ms 5056 KB Output is correct
4 Correct 4 ms 5072 KB Output is correct
5 Correct 5 ms 5072 KB Output is correct
6 Correct 5 ms 5140 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 4 ms 5072 KB Output is correct
9 Correct 3 ms 4944 KB Output is correct
10 Correct 4 ms 5072 KB Output is correct
11 Correct 3 ms 5072 KB Output is correct
12 Correct 3 ms 5072 KB Output is correct
13 Correct 3 ms 5072 KB Output is correct
14 Correct 3 ms 5072 KB Output is correct
15 Correct 3 ms 5072 KB Output is correct
16 Correct 4 ms 5072 KB Output is correct
17 Correct 3 ms 5072 KB Output is correct
18 Correct 5 ms 5200 KB Output is correct
19 Correct 4 ms 5200 KB Output is correct
20 Correct 4 ms 5172 KB Output is correct
21 Correct 3 ms 5072 KB Output is correct
22 Correct 3 ms 5132 KB Output is correct
23 Correct 3 ms 5072 KB Output is correct
24 Correct 3 ms 5072 KB Output is correct
25 Correct 4 ms 5072 KB Output is correct
26 Correct 3 ms 5072 KB Output is correct
27 Correct 5 ms 5072 KB Output is correct
28 Correct 4 ms 5072 KB Output is correct
29 Correct 4 ms 5072 KB Output is correct
30 Correct 3 ms 5120 KB Output is correct
31 Correct 4 ms 5200 KB Output is correct
32 Correct 3 ms 5072 KB Output is correct
33 Correct 4 ms 5168 KB Output is correct
34 Correct 3 ms 5072 KB Output is correct
35 Correct 3 ms 5072 KB Output is correct
36 Correct 3 ms 5200 KB Output is correct
37 Correct 3 ms 5328 KB Output is correct
38 Correct 4 ms 5328 KB Output is correct
39 Correct 4 ms 5156 KB Output is correct
40 Correct 4 ms 5072 KB Output is correct
41 Correct 4 ms 5072 KB Output is correct
42 Correct 4 ms 5140 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 681 ms 9284 KB Output is correct
2 Correct 978 ms 13532 KB Output is correct
3 Correct 884 ms 13536 KB Output is correct
4 Correct 910 ms 13516 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 681 ms 9284 KB Output is correct
2 Correct 978 ms 13532 KB Output is correct
3 Correct 884 ms 13536 KB Output is correct
4 Correct 910 ms 13516 KB Output is correct
5 Correct 818 ms 9532 KB Output is correct
6 Correct 1034 ms 14024 KB Output is correct
7 Correct 1143 ms 14028 KB Output is correct
8 Correct 873 ms 12704 KB Output is correct
9 Correct 523 ms 5328 KB Output is correct
10 Correct 708 ms 5612 KB Output is correct
11 Correct 959 ms 5584 KB Output is correct
12 Correct 763 ms 5456 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 4 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 3 ms 5072 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 4 ms 5072 KB Output is correct
9 Correct 3 ms 5072 KB Output is correct
10 Correct 5 ms 5200 KB Output is correct
11 Correct 4 ms 5200 KB Output is correct
12 Correct 4 ms 5172 KB Output is correct
13 Correct 681 ms 9284 KB Output is correct
14 Correct 978 ms 13532 KB Output is correct
15 Correct 884 ms 13536 KB Output is correct
16 Correct 910 ms 13516 KB Output is correct
17 Correct 818 ms 9532 KB Output is correct
18 Correct 1034 ms 14024 KB Output is correct
19 Correct 1143 ms 14028 KB Output is correct
20 Correct 873 ms 12704 KB Output is correct
21 Correct 523 ms 5328 KB Output is correct
22 Correct 708 ms 5612 KB Output is correct
23 Correct 959 ms 5584 KB Output is correct
24 Correct 763 ms 5456 KB Output is correct
25 Correct 1020 ms 20552 KB Output is correct
26 Correct 1072 ms 20688 KB Output is correct
27 Correct 1124 ms 20744 KB Output is correct
28 Correct 809 ms 17704 KB Output is correct
29 Correct 1014 ms 34768 KB Output is correct
30 Correct 1150 ms 31712 KB Output is correct

Subtask #7
28.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 4 ms 5056 KB Output is correct
4 Correct 4 ms 5072 KB Output is correct
5 Correct 5 ms 5072 KB Output is correct
6 Correct 5 ms 5140 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 4 ms 5072 KB Output is correct
9 Correct 3 ms 4944 KB Output is correct
10 Correct 4 ms 5072 KB Output is correct
11 Correct 3 ms 5072 KB Output is correct
12 Correct 3 ms 5072 KB Output is correct
13 Correct 3 ms 5072 KB Output is correct
14 Correct 3 ms 5072 KB Output is correct
15 Correct 3 ms 5072 KB Output is correct
16 Correct 4 ms 5072 KB Output is correct
17 Correct 3 ms 5072 KB Output is correct
18 Correct 5 ms 5200 KB Output is correct
19 Correct 4 ms 5200 KB Output is correct
20 Correct 4 ms 5172 KB Output is correct
21 Correct 3 ms 5072 KB Output is correct
22 Correct 3 ms 5132 KB Output is correct
23 Correct 3 ms 5072 KB Output is correct
24 Correct 3 ms 5072 KB Output is correct
25 Correct 4 ms 5072 KB Output is correct
26 Correct 3 ms 5072 KB Output is correct
27 Correct 5 ms 5072 KB Output is correct
28 Correct 4 ms 5072 KB Output is correct
29 Correct 4 ms 5072 KB Output is correct
30 Correct 3 ms 5120 KB Output is correct
31 Correct 4 ms 5200 KB Output is correct
32 Correct 3 ms 5072 KB Output is correct
33 Correct 4 ms 5168 KB Output is correct
34 Correct 3 ms 5072 KB Output is correct
35 Correct 3 ms 5072 KB Output is correct
36 Correct 3 ms 5200 KB Output is correct
37 Correct 3 ms 5328 KB Output is correct
38 Correct 4 ms 5328 KB Output is correct
39 Correct 4 ms 5156 KB Output is correct
40 Correct 4 ms 5072 KB Output is correct
41 Correct 4 ms 5072 KB Output is correct
42 Correct 4 ms 5140 KB Output is correct
43 Correct 780 ms 5456 KB Output is correct
44 Correct 976 ms 5516 KB Output is correct
45 Correct 794 ms 5492 KB Output is correct
46 Correct 777 ms 5968 KB Output is correct
47 Correct 789 ms 5964 KB Output is correct
48 Correct 727 ms 5968 KB Output is correct
49 Correct 673 ms 6008 KB Output is correct
50 Correct 844 ms 5712 KB Output is correct
51 Correct 608 ms 5616 KB Output is correct
52 Correct 488 ms 5848 KB Output is correct
53 Correct 748 ms 5912 KB Output is correct
54 Correct 856 ms 5968 KB Output is correct
55 Correct 717 ms 5824 KB Output is correct
56 Correct 844 ms 5880 KB Output is correct
57 Correct 917 ms 5712 KB Output is correct
58 Correct 809 ms 6608 KB Output is correct
59 Correct 857 ms 6728 KB Output is correct
60 Correct 713 ms 6480 KB Output is correct
61 Correct 670 ms 5712 KB Output is correct
62 Correct 860 ms 5456 KB Output is correct
63 Correct 903 ms 5468 KB Output is correct
64 Correct 784 ms 5816 KB Output is correct
65 Correct 428 ms 5312 KB Output is correct
66 Correct 782 ms 5552 KB Output is correct
67 Correct 842 ms 5600 KB Output is correct
68 Correct 840 ms 5456 KB Output is correct

Subtask #8
11.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 4 ms 5056 KB Output is correct
4 Correct 4 ms 5072 KB Output is correct
5 Correct 5 ms 5072 KB Output is correct
6 Correct 5 ms 5140 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 4 ms 5072 KB Output is correct
9 Correct 3 ms 4944 KB Output is correct
10 Correct 4 ms 5072 KB Output is correct
11 Correct 3 ms 5072 KB Output is correct
12 Correct 3 ms 5072 KB Output is correct
13 Correct 3 ms 5072 KB Output is correct
14 Correct 3 ms 5072 KB Output is correct
15 Correct 3 ms 5072 KB Output is correct
16 Correct 4 ms 5072 KB Output is correct
17 Correct 3 ms 5072 KB Output is correct
18 Correct 5 ms 5200 KB Output is correct
19 Correct 4 ms 5200 KB Output is correct
20 Correct 4 ms 5172 KB Output is correct
21 Correct 3 ms 5072 KB Output is correct
22 Correct 3 ms 5132 KB Output is correct
23 Correct 3 ms 5072 KB Output is correct
24 Correct 3 ms 5072 KB Output is correct
25 Correct 4 ms 5072 KB Output is correct
26 Correct 3 ms 5072 KB Output is correct
27 Correct 5 ms 5072 KB Output is correct
28 Correct 4 ms 5072 KB Output is correct
29 Correct 4 ms 5072 KB Output is correct
30 Correct 3 ms 5120 KB Output is correct
31 Correct 4 ms 5200 KB Output is correct
32 Correct 3 ms 5072 KB Output is correct
33 Correct 4 ms 5168 KB Output is correct
34 Correct 3 ms 5072 KB Output is correct
35 Correct 3 ms 5072 KB Output is correct
36 Correct 3 ms 5200 KB Output is correct
37 Correct 3 ms 5328 KB Output is correct
38 Correct 4 ms 5328 KB Output is correct
39 Correct 4 ms 5156 KB Output is correct
40 Correct 4 ms 5072 KB Output is correct
41 Correct 4 ms 5072 KB Output is correct
42 Correct 4 ms 5140 KB Output is correct
43 Correct 681 ms 9284 KB Output is correct
44 Correct 978 ms 13532 KB Output is correct
45 Correct 884 ms 13536 KB Output is correct
46 Correct 910 ms 13516 KB Output is correct
47 Correct 818 ms 9532 KB Output is correct
48 Correct 1034 ms 14024 KB Output is correct
49 Correct 1143 ms 14028 KB Output is correct
50 Correct 873 ms 12704 KB Output is correct
51 Correct 523 ms 5328 KB Output is correct
52 Correct 708 ms 5612 KB Output is correct
53 Correct 959 ms 5584 KB Output is correct
54 Correct 763 ms 5456 KB Output is correct
55 Correct 1020 ms 20552 KB Output is correct
56 Correct 1072 ms 20688 KB Output is correct
57 Correct 1124 ms 20744 KB Output is correct
58 Correct 809 ms 17704 KB Output is correct
59 Correct 1014 ms 34768 KB Output is correct
60 Correct 1150 ms 31712 KB Output is correct
61 Correct 780 ms 5456 KB Output is correct
62 Correct 976 ms 5516 KB Output is correct
63 Correct 794 ms 5492 KB Output is correct
64 Correct 777 ms 5968 KB Output is correct
65 Correct 789 ms 5964 KB Output is correct
66 Correct 727 ms 5968 KB Output is correct
67 Correct 673 ms 6008 KB Output is correct
68 Correct 844 ms 5712 KB Output is correct
69 Correct 608 ms 5616 KB Output is correct
70 Correct 488 ms 5848 KB Output is correct
71 Correct 748 ms 5912 KB Output is correct
72 Correct 856 ms 5968 KB Output is correct
73 Correct 717 ms 5824 KB Output is correct
74 Correct 844 ms 5880 KB Output is correct
75 Correct 917 ms 5712 KB Output is correct
76 Correct 809 ms 6608 KB Output is correct
77 Correct 857 ms 6728 KB Output is correct
78 Correct 713 ms 6480 KB Output is correct
79 Correct 670 ms 5712 KB Output is correct
80 Correct 860 ms 5456 KB Output is correct
81 Correct 903 ms 5468 KB Output is correct
82 Correct 784 ms 5816 KB Output is correct
83 Correct 428 ms 5312 KB Output is correct
84 Correct 782 ms 5552 KB Output is correct
85 Correct 842 ms 5600 KB Output is correct
86 Correct 840 ms 5456 KB Output is correct
87 Correct 3 ms 4944 KB Output is correct
88 Correct 573 ms 20420 KB Output is correct
89 Correct 933 ms 14084 KB Output is correct
90 Correct 892 ms 14296 KB Output is correct
91 Correct 867 ms 20792 KB Output is correct
92 Correct 1115 ms 21372 KB Output is correct
93 Correct 952 ms 21292 KB Output is correct
94 Correct 1016 ms 21292 KB Output is correct
95 Correct 1006 ms 18292 KB Output is correct
96 Correct 1116 ms 13916 KB Output is correct
97 Correct 1235 ms 17296 KB Output is correct
98 Correct 885 ms 23752 KB Output is correct
99 Correct 948 ms 20748 KB Output is correct
100 Correct 947 ms 19592 KB Output is correct
101 Correct 907 ms 18896 KB Output is correct
102 Correct 937 ms 17384 KB Output is correct
103 Correct 927 ms 34768 KB Output is correct
104 Correct 1275 ms 35568 KB Output is correct
105 Correct 1170 ms 32628 KB Output is correct
106 Correct 738 ms 17024 KB Output is correct
107 Correct 946 ms 17372 KB Output is correct
108 Correct 901 ms 17872 KB Output is correct
109 Correct 943 ms 17592 KB Output is correct