oj.uz

Submission #736752

# Submission time Handle Problem Language Result Execution time Memory
736752 2023-05-06T07:53:53 Z onlk97 Digital Circuit (IOI22_circuit) C++17
13 / 100
 950 ms 14628 KB 
#include "circuit.h"
 
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const long long mod=1e9+2022LL;
vector <int> g[200010];
long long sz[200010],d[200010],ac[200010];
int n,dif;
long long weight[100010],a[100010],weightps[100010],seg[400040],laz[400010];
bool marked[100010];
void dfs1(int cur){
    sz[cur]=g[cur].size();
    sz[cur]=max(sz[cur],1LL);
    for (int i:g[cur]){
        dfs1(i);
        sz[cur]*=sz[i];
        sz[cur]%=mod;
    }
    if (!g[cur].size()){
        return;
    } else {
        int fr[g[cur].size()],ba[g[cur].size()];
        for (int i=0; i<g[cur].size(); i++){
            if (!i) fr[i]=sz[g[cur][i]];
            else fr[i]=fr[i-1]*sz[g[cur][i]]%mod;
        }
        for (int i=g[cur].size()-1; i>=0; i--){
            if (i==g[cur].size()-1) ba[i]=sz[g[cur][i]];
            else ba[i]=ba[i+1]*sz[g[cur][i]]%mod;
        }
        for (int i=0; i<g[cur].size(); i++){
            int t=1;
            if (i) t=t*fr[i-1]%mod;
            if (i+1<g[cur].size()) t=t*ba[i+1]%mod;
            d[g[cur][i]]=t;
        }
    }
}
void dfs2(int cur){
    for (int i:g[cur]){
        ac[i]=ac[cur]*d[i]%mod;
        dfs2(i);
    }
}
void build(int id,int tl,int tr){
    if (tl==tr){
        seg[id]=a[tl]*weight[tl];
        return;
    }
    int tm=(tl+tr)/2;
    build(2*id,tl,tm);
    build(2*id+1,tm+1,tr);
    seg[id]=(seg[2*id]+seg[2*id+1])%mod;
}
void pushdown(int id,int tl,int tr){
    if (!marked[id]) return;
    int tm=(tl+tr)/2;
    if (laz[id]%2==1){
        seg[2*id]=(weightps[tm]-weightps[tl-1]+mod-seg[2*id]+mod)%mod;
        seg[2*id+1]=(weightps[tr]-weightps[tm]+mod-seg[2*id+1]+mod)%mod;
    }
    marked[2*id]=1; laz[2*id]+=laz[id];
    marked[2*id+1]=1; laz[2*id+1]+=laz[id];
    marked[id]=0; laz[id]=0;
}
void update(int id,int tl,int tr,int l,int r){
    if (l>r) return;
    if (l<=tl&&tr<=r){
        seg[id]=(weightps[tr]-weightps[tl-1]+mod-seg[id]+mod)%mod;
        laz[id]++;
        marked[id]=1;
        return;
    }
    pushdown(id,tl,tr);
    int tm=(tl+tr)/2;
    update(2*id,tl,tm,l,min(r,tm));
    update(2*id+1,tm+1,tr,max(tm+1,l),r);
    seg[id]=(seg[2*id]+seg[2*id+1])%mod;
}
long long query(int id,int tl,int tr,int l,int r){
    if (l>r) return 0;
    if (l<=tl&&tr<=r) return seg[id];
    pushdown(id,tl,tr);
    int tm=(tl+tr)/2;
    long long lx=query(2*id,tl,tm,l,min(r,tm));
    long long rx=query(2*id+1,tm+1,tr,max(l,tm+1),r);
    return (lx+rx)%mod;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    n=M; dif=N-1;
    for (int i=1; i<N+M; i++) g[P[i]].push_back(i);
    dfs1(0);
    ac[0]=1;
    dfs2(0);
    for (int i=1; i<=n; i++) weight[i]=ac[i+N-1];
    for (int i=1; i<=n; i++) weightps[i]=(weightps[i-1]+weight[i])%mod;
    for (int i=1; i<=n; i++) a[i]=A[i-1];
    build(1,1,n);
}
 
int count_ways(int L, int R) {
    L-=dif; R-=dif;
    update(1,1,n,L,R);
    return query(1,1,n,1,n);
}

Compilation message

circuit.cpp: In function 'void dfs1(int)':
circuit.cpp:24:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         for (int i=0; i<g[cur].size(); i++){
      |                       ~^~~~~~~~~~~~~~
circuit.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |             if (i==g[cur].size()-1) ba[i]=sz[g[cur][i]];
      |                 ~^~~~~~~~~~~~~~~~~
circuit.cpp:32:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for (int i=0; i<g[cur].size(); i++){
      |                       ~^~~~~~~~~~~~~~
circuit.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |             if (i+1<g[cur].size()) t=t*ba[i+1]%mod;
      |                 ~~~^~~~~~~~~~~~~~

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 3 ms 5072 KB Output is correct
4 Correct 4 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 3 ms 5072 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 3 ms 5072 KB Output is correct
3 Correct 4 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 5200 KB Output is correct
8 Correct 3 ms 5200 KB Output is correct
9 Correct 3 ms 5072 KB Output is correct
10 Correct 3 ms 5200 KB Output is correct
11 Correct 3 ms 5200 KB Output is correct
12 Correct 3 ms 5072 KB Output is correct

Subtask #3
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 3 ms 5072 KB Output is correct
4 Correct 4 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 3 ms 5072 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Correct 3 ms 5072 KB Output is correct
11 Correct 4 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 5200 KB Output is correct
16 Correct 3 ms 5200 KB Output is correct
17 Correct 3 ms 5072 KB Output is correct
18 Correct 3 ms 5200 KB Output is correct
19 Correct 3 ms 5200 KB Output is correct
20 Correct 3 ms 5072 KB Output is correct
21 Incorrect 3 ms 5072 KB 1st lines differ - on the 1st token, expected: '759476520', found: '433724394'
22 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 9620 KB Output is correct
2 Correct 837 ms 14156 KB Output is correct
3 Correct 601 ms 14208 KB Output is correct
4 Correct 794 ms 14220 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 9620 KB Output is correct
2 Correct 837 ms 14156 KB Output is correct
3 Correct 601 ms 14208 KB Output is correct
4 Correct 794 ms 14220 KB Output is correct
5 Correct 652 ms 9856 KB Output is correct
6 Incorrect 950 ms 14628 KB 182nd lines differ - on the 1st token, expected: '972396080', found: '121498278'
7 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 3 ms 5072 KB Output is correct
3 Correct 4 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 5200 KB Output is correct
8 Correct 3 ms 5200 KB Output is correct
9 Correct 3 ms 5072 KB Output is correct
10 Correct 3 ms 5200 KB Output is correct
11 Correct 3 ms 5200 KB Output is correct
12 Correct 3 ms 5072 KB Output is correct
13 Correct 484 ms 9620 KB Output is correct
14 Correct 837 ms 14156 KB Output is correct
15 Correct 601 ms 14208 KB Output is correct
16 Correct 794 ms 14220 KB Output is correct
17 Correct 652 ms 9856 KB Output is correct
18 Incorrect 950 ms 14628 KB 182nd lines differ - on the 1st token, expected: '972396080', found: '121498278'
19 Halted 0 ms 0 KB -

Subtask #7
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 3 ms 5072 KB Output is correct
4 Correct 4 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 3 ms 5072 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Correct 3 ms 5072 KB Output is correct
11 Correct 4 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 5200 KB Output is correct
16 Correct 3 ms 5200 KB Output is correct
17 Correct 3 ms 5072 KB Output is correct
18 Correct 3 ms 5200 KB Output is correct
19 Correct 3 ms 5200 KB Output is correct
20 Correct 3 ms 5072 KB Output is correct
21 Incorrect 3 ms 5072 KB 1st lines differ - on the 1st token, expected: '759476520', found: '433724394'
22 Halted 0 ms 0 KB -

Subtask #8
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 3 ms 5072 KB Output is correct
4 Correct 4 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 3 ms 5072 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Correct 3 ms 5072 KB Output is correct
11 Correct 4 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 5200 KB Output is correct
16 Correct 3 ms 5200 KB Output is correct
17 Correct 3 ms 5072 KB Output is correct
18 Correct 3 ms 5200 KB Output is correct
19 Correct 3 ms 5200 KB Output is correct
20 Correct 3 ms 5072 KB Output is correct
21 Incorrect 3 ms 5072 KB 1st lines differ - on the 1st token, expected: '759476520', found: '433724394'
22 Halted 0 ms 0 KB -