oj.uz

Submission #736766

# Submission time Handle Problem Language Result Execution time Memory
736766 2023-05-06T08:02:38 Z onlk97 Digital Circuit (IOI22_circuit) C++17
13 / 100
 1563 ms 21300 KB 
#include "circuit.h"
 
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const long long mod=1e9+2022LL;
vector <int> g[200010];
__int128 sz[200010],d[200010],ac[200010],n,dif;
__int128 weight[100010],a[100010],weightps[100010],seg[400040],laz[400010];
bool marked[100010];
void dfs1(int cur){
    sz[cur]=1;
    if (g[cur].size()>1) sz[cur]=g[cur].size();
    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: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]];
      |                 ~^~~~~~~~~~~~~~~~~
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 4 ms 4944 KB Output is correct
3 Correct 5 ms 5200 KB Output is correct
4 Correct 4 ms 5200 KB Output is correct
5 Correct 6 ms 5228 KB Output is correct
6 Correct 3 ms 5200 KB Output is correct
7 Correct 4 ms 5200 KB Output is correct
8 Correct 4 ms 5200 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4944 KB Output is correct
2 Correct 6 ms 5132 KB Output is correct
3 Correct 4 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 5200 KB Output is correct
7 Correct 5 ms 5312 KB Output is correct
8 Correct 3 ms 5200 KB Output is correct
9 Correct 5 ms 5240 KB Output is correct
10 Correct 6 ms 5328 KB Output is correct
11 Correct 5 ms 5328 KB Output is correct
12 Correct 4 ms 5276 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 4 ms 4944 KB Output is correct
3 Correct 5 ms 5200 KB Output is correct
4 Correct 4 ms 5200 KB Output is correct
5 Correct 6 ms 5228 KB Output is correct
6 Correct 3 ms 5200 KB Output is correct
7 Correct 4 ms 5200 KB Output is correct
8 Correct 4 ms 5200 KB Output is correct
9 Correct 4 ms 4944 KB Output is correct
10 Correct 6 ms 5132 KB Output is correct
11 Correct 4 ms 5072 KB Output is correct
12 Correct 4 ms 5072 KB Output is correct
13 Correct 3 ms 5072 KB Output is correct
14 Correct 3 ms 5200 KB Output is correct
15 Correct 5 ms 5312 KB Output is correct
16 Correct 3 ms 5200 KB Output is correct
17 Correct 5 ms 5240 KB Output is correct
18 Correct 6 ms 5328 KB Output is correct
19 Correct 5 ms 5328 KB Output is correct
20 Correct 4 ms 5276 KB Output is correct
21 Incorrect 5 ms 5328 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 760 ms 12664 KB Output is correct
2 Correct 1563 ms 20252 KB Output is correct
3 Correct 951 ms 20256 KB Output is correct
4 Correct 1121 ms 20260 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 760 ms 12664 KB Output is correct
2 Correct 1563 ms 20252 KB Output is correct
3 Correct 951 ms 20256 KB Output is correct
4 Correct 1121 ms 20260 KB Output is correct
5 Correct 858 ms 13212 KB Output is correct
6 Incorrect 1134 ms 21300 KB 204th lines differ - on the 1st token, expected: '718918906', found: '778560594'
7 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4944 KB Output is correct
2 Correct 6 ms 5132 KB Output is correct
3 Correct 4 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 5200 KB Output is correct
7 Correct 5 ms 5312 KB Output is correct
8 Correct 3 ms 5200 KB Output is correct
9 Correct 5 ms 5240 KB Output is correct
10 Correct 6 ms 5328 KB Output is correct
11 Correct 5 ms 5328 KB Output is correct
12 Correct 4 ms 5276 KB Output is correct
13 Correct 760 ms 12664 KB Output is correct
14 Correct 1563 ms 20252 KB Output is correct
15 Correct 951 ms 20256 KB Output is correct
16 Correct 1121 ms 20260 KB Output is correct
17 Correct 858 ms 13212 KB Output is correct
18 Incorrect 1134 ms 21300 KB 204th lines differ - on the 1st token, expected: '718918906', found: '778560594'
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 4 ms 4944 KB Output is correct
3 Correct 5 ms 5200 KB Output is correct
4 Correct 4 ms 5200 KB Output is correct
5 Correct 6 ms 5228 KB Output is correct
6 Correct 3 ms 5200 KB Output is correct
7 Correct 4 ms 5200 KB Output is correct
8 Correct 4 ms 5200 KB Output is correct
9 Correct 4 ms 4944 KB Output is correct
10 Correct 6 ms 5132 KB Output is correct
11 Correct 4 ms 5072 KB Output is correct
12 Correct 4 ms 5072 KB Output is correct
13 Correct 3 ms 5072 KB Output is correct
14 Correct 3 ms 5200 KB Output is correct
15 Correct 5 ms 5312 KB Output is correct
16 Correct 3 ms 5200 KB Output is correct
17 Correct 5 ms 5240 KB Output is correct
18 Correct 6 ms 5328 KB Output is correct
19 Correct 5 ms 5328 KB Output is correct
20 Correct 4 ms 5276 KB Output is correct
21 Incorrect 5 ms 5328 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 4 ms 4944 KB Output is correct
3 Correct 5 ms 5200 KB Output is correct
4 Correct 4 ms 5200 KB Output is correct
5 Correct 6 ms 5228 KB Output is correct
6 Correct 3 ms 5200 KB Output is correct
7 Correct 4 ms 5200 KB Output is correct
8 Correct 4 ms 5200 KB Output is correct
9 Correct 4 ms 4944 KB Output is correct
10 Correct 6 ms 5132 KB Output is correct
11 Correct 4 ms 5072 KB Output is correct
12 Correct 4 ms 5072 KB Output is correct
13 Correct 3 ms 5072 KB Output is correct
14 Correct 3 ms 5200 KB Output is correct
15 Correct 5 ms 5312 KB Output is correct
16 Correct 3 ms 5200 KB Output is correct
17 Correct 5 ms 5240 KB Output is correct
18 Correct 6 ms 5328 KB Output is correct
19 Correct 5 ms 5328 KB Output is correct
20 Correct 4 ms 5276 KB Output is correct
21 Incorrect 5 ms 5328 KB 1st lines differ - on the 1st token, expected: '759476520', found: '433724394'
22 Halted 0 ms 0 KB -