oj.uz

Submission #627329

# Submission time Handle Problem Language Result Execution time Memory
627329 2022-08-12T12:53:41 Z Cross_Ratio Digital Circuit (IOI22_circuit) C++17
100 / 100
 1352 ms 39616 KB 
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
const long long int p = 1000002022;
const long long int p2 = 2242157;
int N, M;
int P[200005];
int A[200005];
long long int C[200005];
long long int C2[200005];
long long int C223[200005];
long long int DP[200005];
long long int DP2[200005];
long long int DP223[200005];
long long int Vp(long long int n, long long int k) {
    long long int cnt = 0;
    while(n%k==0) {
        n /= k;
        cnt++;
    }
    return cnt;
}
vector<vector<int>> adj;
long long int power(long long int a, long long int b, long long int c) {
    if(b==0) return 1;
    if(b%2==0) {
        long long int k = power(a, b/2, c);
        return k * k % c;
    }
    else {
        return a * power(a, b-1, c) % c;
    }
}
void dfs(int c, int pa) {
    long long int s = 1;
    long long int cnt = 0;
    for(int n : adj[c]) {
        if(n!=pa) cnt++;
    }
    bool isLeaf = (cnt == 0);
    long long int cnt2 = 0, cnt223 = 0;
    if(cnt != 0) {
        while(cnt % 2 == 0) {
            cnt /= 2;
            cnt2++;
        }
        while(cnt % 223 == 0) {
            cnt /= 223;
            cnt223++;
        }
    }
    C[c] = 1;
    if(!isLeaf) {
        C2[c] = cnt2;
        C223[c] = cnt223;
        C[c] = cnt;
    }
    if(pa != -1) {
        C2[c] += C2[pa];
        C223[c] += C223[pa];
        C[c] = C[c] * C[pa] % p;
    }
    DP[c] = 1;
    for(int n : adj[c]) {
        if(n!=pa) {
            dfs(n, c);
            DP[c] = DP[c] * DP[n] % p;
            DP2[c] += DP2[n];
            DP223[c] += DP223[n];
        }
    }
    if(!isLeaf) {
        DP2[c] += cnt2;
        DP223[c] += cnt223;
        DP[c] = DP[c] * cnt % p;
    }
}
long long int B[200005];
long long int D[200005];
long long int sum2(int s, int e) {
    return (D[e] - (s==0?0:D[s-1]) + p) % p;
}
struct SegTree {
    struct Node {
        int lz;
        long long int val;
        Node(int _l, long long int _v) : lz(_l), val(_v) {}
        Node() : lz(0), val(0) {}
    };
    vector<Node> seg;
    int MAX;
    void init(int N) {
        int i;
        for(i=1;i<2*N;i*=2) {}
        seg.resize(i);
        MAX = i;
    }
    void cons() {
        for(int i = MAX/2-1;i>=1;i--) {
            seg[i].val = (seg[2*i].val + seg[2*i+1].val) % p;
        }
    }
    void prop(int n, int ns, int ne) {
        if(seg[n].lz) {
            seg[n].val = (sum2(ns, ne-1) - seg[n].val + p) % p;
            if(n<MAX/2) {
                seg[2*n].lz ^= 1;
                seg[2*n+1].lz ^= 1;
            }
            seg[n].lz = 0;
        }
    }
    void add(int s, int e, int n, int ns, int ne) {
        prop(n,ns,ne);
        if(e<=ns||ne<=s) return;
        if(s<=ns&&ne<=e) {
            seg[n].lz ^= 1;
            prop(n,ns,ne);
            return;
        }
        int mid = ns + ne >> 1;
        add(s,e,2*n,ns,mid);
        add(s,e,2*n+1,mid,ne);
        seg[n].val = (seg[2*n].val + seg[2*n+1].val) % p;
    }
    void add(int s, int e) {
        add(s,e,1,0,MAX/2);
    }
    long long int sum(int s, int e, int n, int ns, int ne) {
        prop(n,ns,ne);
        if(e<=ns||ne<=s) return 0;
        if(s<=ns&&ne<=e) return seg[n].val;
        int mid = ns + ne >> 1;
        return (sum(s,e,2*n,ns,mid) + sum(s,e,2*n+1,mid,ne)) % p;
    }
};
SegTree tree;
void init(int _N, int _M, vector<int> _P, vector<int> _A) {
    N = _N;
    M = _M;
    int i, j;
    adj.resize(N+M);
    for(i=0;i<N+M;i++) {
        P[i] = _P[i];
        if(P[i]!=-1) {
            adj[P[i]].push_back(i);
            adj[i].push_back(P[i]);
        }
    }
    for(i=0;i<M;i++) {
        A[i] = _A[i];
    }
    //cout << "first init\n";
    dfs(0, -1);
    //cout << "dfs done\n";
    for(i=N;i<N+M;i++) {
        long long int c2 = DP2[0] - C2[i];
        long long int c223 = DP223[0] - C223[i];
        long long int cnt = (DP[0] * power(C[i], 222*(p2-1)-1,p)) % p;
        C[i] = cnt;
        C[i] = C[i] * power(2, c2, p) % p;
        C[i] = C[i] * power(223, c223, p) % p;
        //C[i] = (power(C[i],p-2,p) * DP[0]) % p;
    }
    //for(i=0;i<N+M;i++) cout << C[i] << ' ';
    //cout << '\n';
    for(i=0;i<M;i++) B[i] = C[i+N];
    D[0] = B[0];
    for(i=1;i<M;i++) {
        D[i] = (D[i-1] + B[i]) % p;
    }
    //cout << "Tree Turn\n";
    tree.init(M+5);
    int MAX = tree.MAX;
    for(i=0;i<M;i++) {
        tree.seg[i+MAX/2].val = 1LL* A[i] * B[i] % p;
    }
    tree.cons();
    //for(i=0;i<M+N;i++) cout << DP[i] << ' ';
    //cout << '\n';
    //for(i=0;i<M;i++) cout << B[i] << ' ';
    //cout << '\n';
    //cout << "init done\n";
}

int count_ways(int L, int R) {
    L -= N;
    R -= N;
    tree.add(L, R+1);
    return tree.sum(0, tree.MAX/2,1,0,tree.MAX/2);
}

Compilation message

circuit.cpp: In function 'void dfs(int, int)':
circuit.cpp:35:19: warning: unused variable 's' [-Wunused-variable]
   35 |     long long int s = 1;
      |                   ^
circuit.cpp: In member function 'void SegTree::add(int, int, int, int, int)':
circuit.cpp:121:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  121 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
circuit.cpp: In member function 'long long int SegTree::sum(int, int, int, int, int)':
circuit.cpp:133:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  133 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:141:12: warning: unused variable 'j' [-Wunused-variable]
  141 |     int i, j;
      |            ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 372 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 2 ms 464 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 1 ms 464 KB Output is correct
8 Correct 1 ms 464 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 2 ms 464 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 2 ms 720 KB Output is correct
11 Correct 2 ms 720 KB Output is correct
12 Correct 2 ms 592 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 372 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 2 ms 464 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 1 ms 464 KB Output is correct
8 Correct 1 ms 464 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 464 KB Output is correct
12 Correct 1 ms 464 KB Output is correct
13 Correct 2 ms 464 KB Output is correct
14 Correct 1 ms 464 KB Output is correct
15 Correct 2 ms 592 KB Output is correct
16 Correct 2 ms 592 KB Output is correct
17 Correct 2 ms 592 KB Output is correct
18 Correct 2 ms 720 KB Output is correct
19 Correct 2 ms 720 KB Output is correct
20 Correct 2 ms 592 KB Output is correct
21 Correct 2 ms 592 KB Output is correct
22 Correct 2 ms 464 KB Output is correct
23 Correct 2 ms 464 KB Output is correct
24 Correct 2 ms 592 KB Output is correct
25 Correct 2 ms 592 KB Output is correct
26 Correct 2 ms 592 KB Output is correct
27 Correct 2 ms 592 KB Output is correct
28 Correct 2 ms 592 KB Output is correct
29 Correct 2 ms 464 KB Output is correct
30 Correct 1 ms 464 KB Output is correct
31 Correct 1 ms 464 KB Output is correct
32 Correct 1 ms 592 KB Output is correct
33 Correct 1 ms 524 KB Output is correct
34 Correct 1 ms 464 KB Output is correct
35 Correct 1 ms 464 KB Output is correct
36 Correct 1 ms 720 KB Output is correct
37 Correct 1 ms 720 KB Output is correct
38 Correct 1 ms 720 KB Output is correct
39 Correct 1 ms 464 KB Output is correct
40 Correct 1 ms 464 KB Output is correct
41 Correct 2 ms 464 KB Output is correct
42 Correct 2 ms 464 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 734 ms 10224 KB Output is correct
2 Correct 928 ms 20132 KB Output is correct
3 Correct 796 ms 20016 KB Output is correct
4 Correct 972 ms 20020 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 734 ms 10224 KB Output is correct
2 Correct 928 ms 20132 KB Output is correct
3 Correct 796 ms 20016 KB Output is correct
4 Correct 972 ms 20020 KB Output is correct
5 Correct 841 ms 10140 KB Output is correct
6 Correct 1006 ms 20116 KB Output is correct
7 Correct 1137 ms 20092 KB Output is correct
8 Correct 1095 ms 20088 KB Output is correct
9 Correct 238 ms 976 KB Output is correct
10 Correct 1243 ms 1592 KB Output is correct
11 Correct 1121 ms 1592 KB Output is correct
12 Correct 1028 ms 1592 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 2 ms 464 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 2 ms 720 KB Output is correct
11 Correct 2 ms 720 KB Output is correct
12 Correct 2 ms 592 KB Output is correct
13 Correct 734 ms 10224 KB Output is correct
14 Correct 928 ms 20132 KB Output is correct
15 Correct 796 ms 20016 KB Output is correct
16 Correct 972 ms 20020 KB Output is correct
17 Correct 841 ms 10140 KB Output is correct
18 Correct 1006 ms 20116 KB Output is correct
19 Correct 1137 ms 20092 KB Output is correct
20 Correct 1095 ms 20088 KB Output is correct
21 Correct 238 ms 976 KB Output is correct
22 Correct 1243 ms 1592 KB Output is correct
23 Correct 1121 ms 1592 KB Output is correct
24 Correct 1028 ms 1592 KB Output is correct
25 Correct 1245 ms 27892 KB Output is correct
26 Correct 1233 ms 28228 KB Output is correct
27 Correct 1234 ms 28288 KB Output is correct
28 Correct 1027 ms 28256 KB Output is correct
29 Correct 1286 ms 39228 KB Output is correct
30 Correct 838 ms 39236 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 372 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 2 ms 464 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 1 ms 464 KB Output is correct
8 Correct 1 ms 464 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 464 KB Output is correct
12 Correct 1 ms 464 KB Output is correct
13 Correct 2 ms 464 KB Output is correct
14 Correct 1 ms 464 KB Output is correct
15 Correct 2 ms 592 KB Output is correct
16 Correct 2 ms 592 KB Output is correct
17 Correct 2 ms 592 KB Output is correct
18 Correct 2 ms 720 KB Output is correct
19 Correct 2 ms 720 KB Output is correct
20 Correct 2 ms 592 KB Output is correct
21 Correct 2 ms 592 KB Output is correct
22 Correct 2 ms 464 KB Output is correct
23 Correct 2 ms 464 KB Output is correct
24 Correct 2 ms 592 KB Output is correct
25 Correct 2 ms 592 KB Output is correct
26 Correct 2 ms 592 KB Output is correct
27 Correct 2 ms 592 KB Output is correct
28 Correct 2 ms 592 KB Output is correct
29 Correct 2 ms 464 KB Output is correct
30 Correct 1 ms 464 KB Output is correct
31 Correct 1 ms 464 KB Output is correct
32 Correct 1 ms 592 KB Output is correct
33 Correct 1 ms 524 KB Output is correct
34 Correct 1 ms 464 KB Output is correct
35 Correct 1 ms 464 KB Output is correct
36 Correct 1 ms 720 KB Output is correct
37 Correct 1 ms 720 KB Output is correct
38 Correct 1 ms 720 KB Output is correct
39 Correct 1 ms 464 KB Output is correct
40 Correct 1 ms 464 KB Output is correct
41 Correct 2 ms 464 KB Output is correct
42 Correct 2 ms 464 KB Output is correct
43 Correct 582 ms 1184 KB Output is correct
44 Correct 984 ms 1268 KB Output is correct
45 Correct 1084 ms 1232 KB Output is correct
46 Correct 869 ms 1824 KB Output is correct
47 Correct 767 ms 1824 KB Output is correct
48 Correct 1311 ms 1828 KB Output is correct
49 Correct 849 ms 1824 KB Output is correct
50 Correct 552 ms 1824 KB Output is correct
51 Correct 823 ms 1232 KB Output is correct
52 Correct 902 ms 1232 KB Output is correct
53 Correct 775 ms 1360 KB Output is correct
54 Correct 910 ms 1812 KB Output is correct
55 Correct 852 ms 1528 KB Output is correct
56 Correct 758 ms 1412 KB Output is correct
57 Correct 919 ms 1232 KB Output is correct
58 Correct 883 ms 2364 KB Output is correct
59 Correct 948 ms 2388 KB Output is correct
60 Correct 987 ms 2384 KB Output is correct
61 Correct 858 ms 1368 KB Output is correct
62 Correct 908 ms 1172 KB Output is correct
63 Correct 935 ms 1104 KB Output is correct
64 Correct 773 ms 1232 KB Output is correct
65 Correct 464 ms 976 KB Output is correct
66 Correct 848 ms 1616 KB Output is correct
67 Correct 837 ms 1596 KB Output is correct
68 Correct 799 ms 1588 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 372 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 2 ms 464 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 1 ms 464 KB Output is correct
8 Correct 1 ms 464 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 464 KB Output is correct
12 Correct 1 ms 464 KB Output is correct
13 Correct 2 ms 464 KB Output is correct
14 Correct 1 ms 464 KB Output is correct
15 Correct 2 ms 592 KB Output is correct
16 Correct 2 ms 592 KB Output is correct
17 Correct 2 ms 592 KB Output is correct
18 Correct 2 ms 720 KB Output is correct
19 Correct 2 ms 720 KB Output is correct
20 Correct 2 ms 592 KB Output is correct
21 Correct 2 ms 592 KB Output is correct
22 Correct 2 ms 464 KB Output is correct
23 Correct 2 ms 464 KB Output is correct
24 Correct 2 ms 592 KB Output is correct
25 Correct 2 ms 592 KB Output is correct
26 Correct 2 ms 592 KB Output is correct
27 Correct 2 ms 592 KB Output is correct
28 Correct 2 ms 592 KB Output is correct
29 Correct 2 ms 464 KB Output is correct
30 Correct 1 ms 464 KB Output is correct
31 Correct 1 ms 464 KB Output is correct
32 Correct 1 ms 592 KB Output is correct
33 Correct 1 ms 524 KB Output is correct
34 Correct 1 ms 464 KB Output is correct
35 Correct 1 ms 464 KB Output is correct
36 Correct 1 ms 720 KB Output is correct
37 Correct 1 ms 720 KB Output is correct
38 Correct 1 ms 720 KB Output is correct
39 Correct 1 ms 464 KB Output is correct
40 Correct 1 ms 464 KB Output is correct
41 Correct 2 ms 464 KB Output is correct
42 Correct 2 ms 464 KB Output is correct
43 Correct 734 ms 10224 KB Output is correct
44 Correct 928 ms 20132 KB Output is correct
45 Correct 796 ms 20016 KB Output is correct
46 Correct 972 ms 20020 KB Output is correct
47 Correct 841 ms 10140 KB Output is correct
48 Correct 1006 ms 20116 KB Output is correct
49 Correct 1137 ms 20092 KB Output is correct
50 Correct 1095 ms 20088 KB Output is correct
51 Correct 238 ms 976 KB Output is correct
52 Correct 1243 ms 1592 KB Output is correct
53 Correct 1121 ms 1592 KB Output is correct
54 Correct 1028 ms 1592 KB Output is correct
55 Correct 1245 ms 27892 KB Output is correct
56 Correct 1233 ms 28228 KB Output is correct
57 Correct 1234 ms 28288 KB Output is correct
58 Correct 1027 ms 28256 KB Output is correct
59 Correct 1286 ms 39228 KB Output is correct
60 Correct 838 ms 39236 KB Output is correct
61 Correct 582 ms 1184 KB Output is correct
62 Correct 984 ms 1268 KB Output is correct
63 Correct 1084 ms 1232 KB Output is correct
64 Correct 869 ms 1824 KB Output is correct
65 Correct 767 ms 1824 KB Output is correct
66 Correct 1311 ms 1828 KB Output is correct
67 Correct 849 ms 1824 KB Output is correct
68 Correct 552 ms 1824 KB Output is correct
69 Correct 823 ms 1232 KB Output is correct
70 Correct 902 ms 1232 KB Output is correct
71 Correct 775 ms 1360 KB Output is correct
72 Correct 910 ms 1812 KB Output is correct
73 Correct 852 ms 1528 KB Output is correct
74 Correct 758 ms 1412 KB Output is correct
75 Correct 919 ms 1232 KB Output is correct
76 Correct 883 ms 2364 KB Output is correct
77 Correct 948 ms 2388 KB Output is correct
78 Correct 987 ms 2384 KB Output is correct
79 Correct 858 ms 1368 KB Output is correct
80 Correct 908 ms 1172 KB Output is correct
81 Correct 935 ms 1104 KB Output is correct
82 Correct 773 ms 1232 KB Output is correct
83 Correct 464 ms 976 KB Output is correct
84 Correct 848 ms 1616 KB Output is correct
85 Correct 837 ms 1596 KB Output is correct
86 Correct 799 ms 1588 KB Output is correct
87 Correct 1 ms 336 KB Output is correct
88 Correct 600 ms 25480 KB Output is correct
89 Correct 921 ms 17468 KB Output is correct
90 Correct 1010 ms 17236 KB Output is correct
91 Correct 981 ms 28472 KB Output is correct
92 Correct 1171 ms 28592 KB Output is correct
93 Correct 1140 ms 28588 KB Output is correct
94 Correct 1219 ms 28472 KB Output is correct
95 Correct 1292 ms 28488 KB Output is correct
96 Correct 1014 ms 17336 KB Output is correct
97 Correct 1099 ms 17328 KB Output is correct
98 Correct 807 ms 22644 KB Output is correct
99 Correct 1092 ms 28260 KB Output is correct
100 Correct 1052 ms 22628 KB Output is correct
101 Correct 1272 ms 20164 KB Output is correct
102 Correct 1192 ms 17436 KB Output is correct
103 Correct 1352 ms 39216 KB Output is correct
104 Correct 1111 ms 39616 KB Output is correct
105 Correct 1200 ms 39612 KB Output is correct
106 Correct 1012 ms 18748 KB Output is correct
107 Correct 1227 ms 17496 KB Output is correct
108 Correct 1068 ms 17816 KB Output is correct
109 Correct 1069 ms 17524 KB Output is correct