oj.uz

Submission #1025247

# Submission time Handle Problem Language Result Execution time Memory
1025247 2024-07-16T18:17:51 Z Wansur Digital Circuit (IOI22_circuit) C++17
52 / 100
 868 ms 35940 KB 
#include <bits/stdc++.h>
#define ent '\n'
#define f first
#define s second

using namespace std;
typedef long long ll;
const int maxn = 2e5 + 12;
const int mod = 1e9 + 2022;

pair<ll, ll> t[maxn*4];
vector<int> g[maxn];
ll dp[maxn];
ll mul[maxn];
int a[maxn];
int p[maxn];
int n, m;

void calc(int v, int p){
    dp[v] = max(1, (int)g[v].size());
    for(int to:g[v]){
        calc(to, v);
        dp[v] = dp[v] * dp[to] % mod;
    }
}

void dfs(int v, int p){
    if(!mul[v]) mul[v] = 1;
    vector<int> suff;
    for(int i=0;i<g[v].size();i++){
        suff.push_back(dp[g[v][i]]);
    }
    suff.push_back(1);
    for(int i=(int)suff.size()-2;i>=0;i--){
        suff[i] = suff[i] * suff[i+1] % mod;
    }
    ll pref = 1;
    for(int i=0;i<g[v].size();i++){
        int to = g[v][i];
        mul[to] = pref * suff[i+1] % mod * mul[v] % mod;
        dfs(to, v);
        pref = pref * dp[to] % mod;
    }

}

void build(int v, int tl, int tr){
    p[v] = 0;
    if(tl == tr){
        if(a[tl]){
            t[v] = {0, mul[tl+m-1]};
        }
        else{
            t[v] = {mul[tl+m-1], 0};
        }
    }
    else{
        int mid = tl + tr >> 1;
        build(v*2, tl, mid);
        build(v*2+1, mid+1, tr);
        t[v].f = (t[v*2].f + t[v*2+1].f) % mod;
        t[v].s = (t[v*2].s + t[v*2+1].s) % mod;
    }
}

void push(int v, int tl, int tr){
    if(tl == tr || !p[v]){
        return;
    }
    p[v*2] ^= 1;
    p[v*2+1] ^= 1;
    swap(t[v*2].f, t[v*2].s);
    swap(t[v*2+1].f, t[v*2+1].s);
    p[v] = 0;
}

void upd(int v, int tl, int tr, int l, int r){
    push(v, tl, tr);
    if(tl > r || l > tr){
        return;
    }
    if(tl >= l && tr <= r){
        swap(t[v].f, t[v].s);
        p[v] = 1;
        return;
    }
    int mid = tl + tr >> 1;
    upd(v*2, tl, mid, l, r);
    upd(v*2+1, mid+1, tr, l, r);
    t[v].f = (t[v*2].f + t[v*2+1].f) % mod;
    t[v].s = (t[v*2].s + t[v*2+1].s) % mod;
}

void init(int N, int M, std::vector<int> p, std::vector<int> A){
    m = N, n = M;
    for(int i=1;i<n+m;i++){
        g[p[i]].push_back(i);
    }
    for(int i=1;i<=n;i++){
        a[i] = A[i-1];
    }
    calc(0, -1);
    dfs(0, -1);
    build(1, 1, n);
}

int count_ways(int L, int R){
    L -= m - 1, R -= m - 1;
    upd(1, 1, n, L, R);
    return t[1].s;
}

Compilation message

circuit.cpp: In function 'void dfs(int, int)':
circuit.cpp:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i=0;i<g[v].size();i++){
      |                 ~^~~~~~~~~~~~
circuit.cpp:38:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i=0;i<g[v].size();i++){
      |                 ~^~~~~~~~~~~~
circuit.cpp: In function 'void build(int, int, int)':
circuit.cpp:58:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |         int mid = tl + tr >> 1;
      |                   ~~~^~~~
circuit.cpp: In function 'void upd(int, int, int, int, int)':
circuit.cpp:87:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |     int mid = tl + tr >> 1;
      |               ~~~^~~~

Subtask #1
2.0 / 2.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10584 KB Output is correct
3 Correct 3 ms 10584 KB Output is correct
4 Correct 2 ms 10584 KB Output is correct
5 Correct 2 ms 10584 KB Output is correct
6 Correct 2 ms 10584 KB Output is correct
7 Correct 2 ms 10700 KB Output is correct
8 Correct 2 ms 10584 KB Output is correct
9 Correct 2 ms 10584 KB Output is correct
10 Correct 2 ms 10840 KB Output is correct
11 Correct 2 ms 10840 KB Output is correct
12 Correct 2 ms 10584 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10584 KB Output is correct
3 Correct 2 ms 10636 KB Output is correct
4 Correct 2 ms 10584 KB Output is correct
5 Correct 2 ms 10584 KB Output is correct
6 Correct 2 ms 10584 KB Output is correct
7 Correct 2 ms 10584 KB Output is correct
8 Correct 2 ms 10584 KB Output is correct
9 Correct 2 ms 10584 KB Output is correct
10 Correct 2 ms 10584 KB Output is correct
11 Correct 3 ms 10584 KB Output is correct
12 Correct 2 ms 10584 KB Output is correct
13 Correct 2 ms 10584 KB Output is correct
14 Correct 2 ms 10584 KB Output is correct
15 Correct 2 ms 10700 KB Output is correct
16 Correct 2 ms 10584 KB Output is correct
17 Correct 2 ms 10584 KB Output is correct
18 Correct 2 ms 10840 KB Output is correct
19 Correct 2 ms 10840 KB Output is correct
20 Correct 2 ms 10584 KB Output is correct
21 Incorrect 2 ms 10584 KB 1st lines differ - on the 1st token, expected: '759476520', found: '770369124'
22 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 12632 KB Output is correct
2 Correct 690 ms 16468 KB Output is correct
3 Correct 750 ms 16340 KB Output is correct
4 Correct 707 ms 16332 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 12632 KB Output is correct
2 Correct 690 ms 16468 KB Output is correct
3 Correct 750 ms 16340 KB Output is correct
4 Correct 707 ms 16332 KB Output is correct
5 Correct 630 ms 12632 KB Output is correct
6 Correct 748 ms 16464 KB Output is correct
7 Correct 794 ms 16464 KB Output is correct
8 Correct 773 ms 16340 KB Output is correct
9 Correct 351 ms 10584 KB Output is correct
10 Correct 652 ms 10840 KB Output is correct
11 Correct 737 ms 10840 KB Output is correct
12 Correct 590 ms 10840 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10584 KB Output is correct
3 Correct 3 ms 10584 KB Output is correct
4 Correct 2 ms 10584 KB Output is correct
5 Correct 2 ms 10584 KB Output is correct
6 Correct 2 ms 10584 KB Output is correct
7 Correct 2 ms 10700 KB Output is correct
8 Correct 2 ms 10584 KB Output is correct
9 Correct 2 ms 10584 KB Output is correct
10 Correct 2 ms 10840 KB Output is correct
11 Correct 2 ms 10840 KB Output is correct
12 Correct 2 ms 10584 KB Output is correct
13 Correct 513 ms 12632 KB Output is correct
14 Correct 690 ms 16468 KB Output is correct
15 Correct 750 ms 16340 KB Output is correct
16 Correct 707 ms 16332 KB Output is correct
17 Correct 630 ms 12632 KB Output is correct
18 Correct 748 ms 16464 KB Output is correct
19 Correct 794 ms 16464 KB Output is correct
20 Correct 773 ms 16340 KB Output is correct
21 Correct 351 ms 10584 KB Output is correct
22 Correct 652 ms 10840 KB Output is correct
23 Correct 737 ms 10840 KB Output is correct
24 Correct 590 ms 10840 KB Output is correct
25 Correct 776 ms 20296 KB Output is correct
26 Correct 843 ms 20272 KB Output is correct
27 Correct 842 ms 20304 KB Output is correct
28 Correct 552 ms 20304 KB Output is correct
29 Correct 868 ms 35920 KB Output is correct
30 Correct 727 ms 35940 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10584 KB Output is correct
3 Correct 2 ms 10636 KB Output is correct
4 Correct 2 ms 10584 KB Output is correct
5 Correct 2 ms 10584 KB Output is correct
6 Correct 2 ms 10584 KB Output is correct
7 Correct 2 ms 10584 KB Output is correct
8 Correct 2 ms 10584 KB Output is correct
9 Correct 2 ms 10584 KB Output is correct
10 Correct 2 ms 10584 KB Output is correct
11 Correct 3 ms 10584 KB Output is correct
12 Correct 2 ms 10584 KB Output is correct
13 Correct 2 ms 10584 KB Output is correct
14 Correct 2 ms 10584 KB Output is correct
15 Correct 2 ms 10700 KB Output is correct
16 Correct 2 ms 10584 KB Output is correct
17 Correct 2 ms 10584 KB Output is correct
18 Correct 2 ms 10840 KB Output is correct
19 Correct 2 ms 10840 KB Output is correct
20 Correct 2 ms 10584 KB Output is correct
21 Incorrect 2 ms 10584 KB 1st lines differ - on the 1st token, expected: '759476520', found: '770369124'
22 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10584 KB Output is correct
3 Correct 2 ms 10636 KB Output is correct
4 Correct 2 ms 10584 KB Output is correct
5 Correct 2 ms 10584 KB Output is correct
6 Correct 2 ms 10584 KB Output is correct
7 Correct 2 ms 10584 KB Output is correct
8 Correct 2 ms 10584 KB Output is correct
9 Correct 2 ms 10584 KB Output is correct
10 Correct 2 ms 10584 KB Output is correct
11 Correct 3 ms 10584 KB Output is correct
12 Correct 2 ms 10584 KB Output is correct
13 Correct 2 ms 10584 KB Output is correct
14 Correct 2 ms 10584 KB Output is correct
15 Correct 2 ms 10700 KB Output is correct
16 Correct 2 ms 10584 KB Output is correct
17 Correct 2 ms 10584 KB Output is correct
18 Correct 2 ms 10840 KB Output is correct
19 Correct 2 ms 10840 KB Output is correct
20 Correct 2 ms 10584 KB Output is correct
21 Incorrect 2 ms 10584 KB 1st lines differ - on the 1st token, expected: '759476520', found: '770369124'
22 Halted 0 ms 0 KB -