oj.uz

Submission #627303

# Submission time Handle Problem Language Result Execution time Memory
627303 2022-08-12T12:29:46 Z Cross_Ratio Digital Circuit (IOI22_circuit) C++17
52 / 100
 1225 ms 39232 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], p2-2, p2)) % p2;
        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 = 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 1 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 468 KB Output is correct

Subtask #2
7.0 / 7.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 1 ms 464 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 1 ms 720 KB Output is correct
11 Correct 1 ms 720 KB Output is correct
12 Correct 1 ms 540 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 1 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 468 KB Output is correct
9 Correct 0 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 1 ms 464 KB Output is correct
14 Correct 1 ms 464 KB Output is correct
15 Correct 1 ms 592 KB Output is correct
16 Correct 1 ms 592 KB Output is correct
17 Correct 1 ms 592 KB Output is correct
18 Correct 1 ms 720 KB Output is correct
19 Correct 1 ms 720 KB Output is correct
20 Correct 1 ms 540 KB Output is correct
21 Incorrect 1 ms 592 KB 1st lines differ - on the 1st token, expected: '759476520', found: '844678486'
22 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 622 ms 10176 KB Output is correct
2 Correct 876 ms 20120 KB Output is correct
3 Correct 995 ms 20064 KB Output is correct
4 Correct 848 ms 20088 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 622 ms 10176 KB Output is correct
2 Correct 876 ms 20120 KB Output is correct
3 Correct 995 ms 20064 KB Output is correct
4 Correct 848 ms 20088 KB Output is correct
5 Correct 653 ms 10160 KB Output is correct
6 Correct 1012 ms 20012 KB Output is correct
7 Correct 903 ms 20008 KB Output is correct
8 Correct 936 ms 20092 KB Output is correct
9 Correct 265 ms 952 KB Output is correct
10 Correct 821 ms 1596 KB Output is correct
11 Correct 819 ms 1596 KB Output is correct
12 Correct 775 ms 1592 KB Output is correct

Subtask #6
27.0 / 27.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 1 ms 464 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 1 ms 720 KB Output is correct
11 Correct 1 ms 720 KB Output is correct
12 Correct 1 ms 540 KB Output is correct
13 Correct 622 ms 10176 KB Output is correct
14 Correct 876 ms 20120 KB Output is correct
15 Correct 995 ms 20064 KB Output is correct
16 Correct 848 ms 20088 KB Output is correct
17 Correct 653 ms 10160 KB Output is correct
18 Correct 1012 ms 20012 KB Output is correct
19 Correct 903 ms 20008 KB Output is correct
20 Correct 936 ms 20092 KB Output is correct
21 Correct 265 ms 952 KB Output is correct
22 Correct 821 ms 1596 KB Output is correct
23 Correct 819 ms 1596 KB Output is correct
24 Correct 775 ms 1592 KB Output is correct
25 Correct 998 ms 27880 KB Output is correct
26 Correct 1074 ms 28188 KB Output is correct
27 Correct 1225 ms 28260 KB Output is correct
28 Correct 912 ms 28228 KB Output is correct
29 Correct 1006 ms 39212 KB Output is correct
30 Correct 870 ms 39232 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 1 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 468 KB Output is correct
9 Correct 0 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 1 ms 464 KB Output is correct
14 Correct 1 ms 464 KB Output is correct
15 Correct 1 ms 592 KB Output is correct
16 Correct 1 ms 592 KB Output is correct
17 Correct 1 ms 592 KB Output is correct
18 Correct 1 ms 720 KB Output is correct
19 Correct 1 ms 720 KB Output is correct
20 Correct 1 ms 540 KB Output is correct
21 Incorrect 1 ms 592 KB 1st lines differ - on the 1st token, expected: '759476520', found: '844678486'
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 1 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 468 KB Output is correct
9 Correct 0 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 1 ms 464 KB Output is correct
14 Correct 1 ms 464 KB Output is correct
15 Correct 1 ms 592 KB Output is correct
16 Correct 1 ms 592 KB Output is correct
17 Correct 1 ms 592 KB Output is correct
18 Correct 1 ms 720 KB Output is correct
19 Correct 1 ms 720 KB Output is correct
20 Correct 1 ms 540 KB Output is correct
21 Incorrect 1 ms 592 KB 1st lines differ - on the 1st token, expected: '759476520', found: '844678486'
22 Halted 0 ms 0 KB -