oj.uz

Submission #736771

# Submission time Handle Problem Language Result Execution time Memory
736771 2023-05-06T08:09:26 Z onlk97 Digital Circuit (IOI22_circuit) C++17
13 / 100
 936 ms 14624 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],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);
    sz[cur]%=mod;
    for (int i:g[cur]){
        dfs1(i);
        sz[cur]=sz[cur]*sz[i]%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]]%mod;
            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]]%mod;
            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%mod;
        }
    }
}
void dfs2(int cur){
    for (int i:g[cur]){
        ac[i]=ac[cur]%mod*d[i]%mod;
        dfs2(i);
    }
}
void build(int id,int tl,int tr){
    if (tl==tr){
        seg[id]=a[tl]*weight[tl]%mod;
        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]%mod;
    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)%mod;
}

Compilation message

circuit.cpp: In function 'void dfs1(int)':
circuit.cpp:23:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         for (int i=0; i<g[cur].size(); i++){
      |                       ~^~~~~~~~~~~~~~
circuit.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |             if (i==g[cur].size()-1) ba[i]=sz[g[cur][i]]%mod;
      |                 ~^~~~~~~~~~~~~~~~~
circuit.cpp:31:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for (int i=0; i<g[cur].size(); i++){
      |                       ~^~~~~~~~~~~~~~
circuit.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |             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 5032 KB Output is correct
3 Correct 3 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 5072 KB Output is correct
8 Correct 4 ms 5072 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 5072 KB Output is correct
3 Correct 3 ms 5072 KB Output is correct
4 Correct 3 ms 5124 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 3 ms 5160 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 5192 KB Output is correct
10 Correct 4 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 5032 KB Output is correct
3 Correct 3 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 5072 KB Output is correct
8 Correct 4 ms 5072 KB Output is correct
9 Correct 3 ms 4944 KB Output is correct
10 Correct 3 ms 5072 KB Output is correct
11 Correct 3 ms 5072 KB Output is correct
12 Correct 3 ms 5124 KB Output is correct
13 Correct 3 ms 5072 KB Output is correct
14 Correct 3 ms 5160 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 5192 KB Output is correct
18 Correct 4 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 4 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 630 ms 9588 KB Output is correct
2 Correct 884 ms 14192 KB Output is correct
3 Correct 911 ms 14152 KB Output is correct
4 Correct 903 ms 14232 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 630 ms 9588 KB Output is correct
2 Correct 884 ms 14192 KB Output is correct
3 Correct 911 ms 14152 KB Output is correct
4 Correct 903 ms 14232 KB Output is correct
5 Correct 700 ms 9856 KB Output is correct
6 Incorrect 936 ms 14624 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 3 ms 4944 KB Output is correct
2 Correct 3 ms 5072 KB Output is correct
3 Correct 3 ms 5072 KB Output is correct
4 Correct 3 ms 5124 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 3 ms 5160 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 5192 KB Output is correct
10 Correct 4 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 630 ms 9588 KB Output is correct
14 Correct 884 ms 14192 KB Output is correct
15 Correct 911 ms 14152 KB Output is correct
16 Correct 903 ms 14232 KB Output is correct
17 Correct 700 ms 9856 KB Output is correct
18 Incorrect 936 ms 14624 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 5032 KB Output is correct
3 Correct 3 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 5072 KB Output is correct
8 Correct 4 ms 5072 KB Output is correct
9 Correct 3 ms 4944 KB Output is correct
10 Correct 3 ms 5072 KB Output is correct
11 Correct 3 ms 5072 KB Output is correct
12 Correct 3 ms 5124 KB Output is correct
13 Correct 3 ms 5072 KB Output is correct
14 Correct 3 ms 5160 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 5192 KB Output is correct
18 Correct 4 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 4 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 5032 KB Output is correct
3 Correct 3 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 5072 KB Output is correct
8 Correct 4 ms 5072 KB Output is correct
9 Correct 3 ms 4944 KB Output is correct
10 Correct 3 ms 5072 KB Output is correct
11 Correct 3 ms 5072 KB Output is correct
12 Correct 3 ms 5124 KB Output is correct
13 Correct 3 ms 5072 KB Output is correct
14 Correct 3 ms 5160 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 5192 KB Output is correct
18 Correct 4 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 4 ms 5072 KB 1st lines differ - on the 1st token, expected: '759476520', found: '433724394'
22 Halted 0 ms 0 KB -