oj.uz

Submission #627316

# Submission time Handle Problem Language Result Execution time Memory
627316 2022-08-12T12:47:31 Z Cross_Ratio Digital Circuit (IOI22_circuit) C++17
52 / 100
 1180 ms 39208 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] % p2;
    }
    DP[c] = 1;
    for(int n : adj[c]) {
        if(n!=pa) {
            dfs(n, c);
            DP[c] = DP[c] * DP[n] % p2;
            DP2[c] += DP2[n];
            DP223[c] += DP223[n];
        }
    }
    if(!isLeaf) {
        DP2[c] += cnt2;
        DP223[c] += cnt223;
        DP[c] = DP[c] * cnt % p2;
    }
}
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 0 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 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 2 ms 464 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 1 ms 464 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 2 ms 640 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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 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 2 ms 464 KB Output is correct
12 Correct 1 ms 464 KB Output is correct
13 Correct 1 ms 464 KB Output is correct
14 Correct 2 ms 464 KB Output is correct
15 Correct 2 ms 592 KB Output is correct
16 Correct 2 ms 640 KB Output is correct
17 Correct 2 ms 640 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 Incorrect 2 ms 592 KB 1st lines differ - on the 1st token, expected: '759476520', found: '19564710'
22 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 644 ms 10232 KB Output is correct
2 Correct 1084 ms 20080 KB Output is correct
3 Correct 911 ms 20088 KB Output is correct
4 Correct 675 ms 20060 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 644 ms 10232 KB Output is correct
2 Correct 1084 ms 20080 KB Output is correct
3 Correct 911 ms 20088 KB Output is correct
4 Correct 675 ms 20060 KB Output is correct
5 Correct 735 ms 10192 KB Output is correct
6 Correct 965 ms 20160 KB Output is correct
7 Correct 899 ms 20088 KB Output is correct
8 Correct 907 ms 20020 KB Output is correct
9 Correct 483 ms 976 KB Output is correct
10 Correct 936 ms 1600 KB Output is correct
11 Correct 925 ms 1592 KB Output is correct
12 Correct 965 ms 1600 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 2 ms 464 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 1 ms 464 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 2 ms 640 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 644 ms 10232 KB Output is correct
14 Correct 1084 ms 20080 KB Output is correct
15 Correct 911 ms 20088 KB Output is correct
16 Correct 675 ms 20060 KB Output is correct
17 Correct 735 ms 10192 KB Output is correct
18 Correct 965 ms 20160 KB Output is correct
19 Correct 899 ms 20088 KB Output is correct
20 Correct 907 ms 20020 KB Output is correct
21 Correct 483 ms 976 KB Output is correct
22 Correct 936 ms 1600 KB Output is correct
23 Correct 925 ms 1592 KB Output is correct
24 Correct 965 ms 1600 KB Output is correct
25 Correct 1067 ms 27888 KB Output is correct
26 Correct 1180 ms 28188 KB Output is correct
27 Correct 1098 ms 28360 KB Output is correct
28 Correct 821 ms 28256 KB Output is correct
29 Correct 1061 ms 39208 KB Output is correct
30 Correct 972 ms 39208 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 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 2 ms 464 KB Output is correct
12 Correct 1 ms 464 KB Output is correct
13 Correct 1 ms 464 KB Output is correct
14 Correct 2 ms 464 KB Output is correct
15 Correct 2 ms 592 KB Output is correct
16 Correct 2 ms 640 KB Output is correct
17 Correct 2 ms 640 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 Incorrect 2 ms 592 KB 1st lines differ - on the 1st token, expected: '759476520', found: '19564710'
22 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 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 2 ms 464 KB Output is correct
12 Correct 1 ms 464 KB Output is correct
13 Correct 1 ms 464 KB Output is correct
14 Correct 2 ms 464 KB Output is correct
15 Correct 2 ms 592 KB Output is correct
16 Correct 2 ms 640 KB Output is correct
17 Correct 2 ms 640 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 Incorrect 2 ms 592 KB 1st lines differ - on the 1st token, expected: '759476520', found: '19564710'
22 Halted 0 ms 0 KB -