oj.uz

Submission #629944

# Submission time Handle Problem Language Result Execution time Memory
629944 2022-08-15T11:45:48 Z jeff252 Digital Circuit (IOI22_circuit) C++17
52 / 100
 1047 ms 48456 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e6+10;
const int SS=1<<18;
const int INFi=2e9;
const ll INFl=1e13;
const ll mod2=998244353;
const ll mod=1000002022;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=20;
int t[N],n;
vi graf[N];
ll dp[N],il[N],xd[N],seg[(SS<<1)+10][2];
bool lazy[(SS<<1)+10],wl[N];
void dfs1(int v){
    il[v]=graf[v].size();
    if(graf[v].size()==0) il[v]=1;
    for(auto u:graf[v]){
        dfs1(u);
        (il[v]*=il[u])%=mod;
    }
}
void dfs2(int v,ll val){
    dp[v]=val;
    xd[graf[v].size()]=1;
    for(int i2=graf[v].size()-1;i2>=0;i2--){
        xd[i2]=xd[i2+1]*il[graf[v][i2]]; 
        xd[i2]%=mod;
    }
    ll curr=1;
    for(int i2=0;i2<graf[v].size();i2++){
        auto u=graf[v][i2];
        dfs2(u,(((val*curr)%mod)*xd[i2+1])%mod);
        (curr=curr*il[u])%=mod;
    }
}
void push(int v){
    if(lazy[v]){
        lazy[v]=0;
        lazy[(v<<1)]^=1,lazy[(v<<1)+1]^=1;
        swap(seg[(v<<1)+1][0],seg[(v<<1)+1][1]);
        swap(seg[(v<<1)][0],seg[(v<<1)][1]);
    }
}
void upd(int a,int b,int p=0,int k=SS-1,int v=1){
    if(p>b or k<a) return;
    if(p>=a and k<=b){
        lazy[v]^=1;
        swap(seg[v][0],seg[v][1]);
        return;
    }
    push(v);
    int sr=(p+k)>>1;
    upd(a,b,p,sr,(v<<1)),upd(a,b,sr+1,k,(v<<1)+1);
    (seg[v][0]=seg[(v<<1)][0]+seg[(v<<1)+1][0])%=mod;
    (seg[v][1]=seg[(v<<1)][1]+seg[(v<<1)+1][1])%=mod;
}
void uzu(int v){
    if(v>=SS){
        if(wl[v-SS]) seg[v][1]=dp[v-SS+n];
        else seg[v][0]=dp[v-SS+n];
        return; 
    }
    uzu((v<<1)),uzu((v<<1)+1);
    (seg[v][0]=seg[(v<<1)][0]+seg[(v<<1)+1][0])%=mod;
    (seg[v][1]=seg[(v<<1)][1]+seg[(v<<1)+1][1])%=mod;
}
void init(int n2,int m,vi p,vi a){
    n=n2;
    for(int i=1;i<n+m;i++) graf[p[i]+1].push_back(i+1);
    dfs1(1);
    dfs2(1,1);
    for(int i=0;i<a.size();i++) wl[i+1]=a[i];
    uzu(1);
}
int count_ways(int l,int r){
    l++,r++;
    l-=n,r-=n;
    upd(l,r);
    return seg[1][1];
}
/*int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int n2,m2;
    cin>>n2>>m2;
    vi p,a;
    for(int i=0;i<n2+m2;i++){
        int d;
        cin>>d;
        p.push_back(d);
    }
    for(int i=0;i<m2;i++){
        int d;
        cin>>d;
        a.push_back(d);  
    }
    init(n2,m2,p,a);
    int q;
    cin>>q;
    while(q--){
        int l,r;
        cin>>l>>r;
        cout<<count_ways(l,r)<<"\n";
    }
}*/

Compilation message

circuit.cpp: In function 'void dfs2(int, ll)':
circuit.cpp:40:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i2=0;i2<graf[v].size();i2++){
      |                  ~~^~~~~~~~~~~~~~~
circuit.cpp: In function 'void init(int, int, vi, vi)':
circuit.cpp:82:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for(int i=0;i<a.size();i++) wl[i+1]=a[i];
      |                 ~^~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31952 KB Output is correct
2 Correct 18 ms 31952 KB Output is correct
3 Correct 18 ms 31984 KB Output is correct
4 Correct 19 ms 32092 KB Output is correct
5 Correct 20 ms 32080 KB Output is correct
6 Correct 22 ms 32092 KB Output is correct
7 Correct 22 ms 32104 KB Output is correct
8 Correct 21 ms 32084 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 32004 KB Output is correct
2 Correct 17 ms 31952 KB Output is correct
3 Correct 17 ms 32096 KB Output is correct
4 Correct 19 ms 32080 KB Output is correct
5 Correct 18 ms 31984 KB Output is correct
6 Correct 17 ms 32036 KB Output is correct
7 Correct 19 ms 32044 KB Output is correct
8 Correct 19 ms 32080 KB Output is correct
9 Correct 18 ms 32064 KB Output is correct
10 Correct 18 ms 32212 KB Output is correct
11 Correct 18 ms 32208 KB Output is correct
12 Correct 18 ms 32056 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31952 KB Output is correct
2 Correct 18 ms 31952 KB Output is correct
3 Correct 18 ms 31984 KB Output is correct
4 Correct 19 ms 32092 KB Output is correct
5 Correct 20 ms 32080 KB Output is correct
6 Correct 22 ms 32092 KB Output is correct
7 Correct 22 ms 32104 KB Output is correct
8 Correct 21 ms 32084 KB Output is correct
9 Correct 19 ms 32004 KB Output is correct
10 Correct 17 ms 31952 KB Output is correct
11 Correct 17 ms 32096 KB Output is correct
12 Correct 19 ms 32080 KB Output is correct
13 Correct 18 ms 31984 KB Output is correct
14 Correct 17 ms 32036 KB Output is correct
15 Correct 19 ms 32044 KB Output is correct
16 Correct 19 ms 32080 KB Output is correct
17 Correct 18 ms 32064 KB Output is correct
18 Correct 18 ms 32212 KB Output is correct
19 Correct 18 ms 32208 KB Output is correct
20 Correct 18 ms 32056 KB Output is correct
21 Incorrect 18 ms 32080 KB 1st lines differ - on the 1st token, expected: '759476520', found: '966416300'
22 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 34820 KB Output is correct
2 Correct 784 ms 37604 KB Output is correct
3 Correct 674 ms 37704 KB Output is correct
4 Correct 1035 ms 37704 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 34820 KB Output is correct
2 Correct 784 ms 37604 KB Output is correct
3 Correct 674 ms 37704 KB Output is correct
4 Correct 1035 ms 37704 KB Output is correct
5 Correct 756 ms 34896 KB Output is correct
6 Correct 1004 ms 37700 KB Output is correct
7 Correct 1047 ms 37728 KB Output is correct
8 Correct 957 ms 37688 KB Output is correct
9 Correct 485 ms 32224 KB Output is correct
10 Correct 746 ms 32412 KB Output is correct
11 Correct 908 ms 32400 KB Output is correct
12 Correct 724 ms 32428 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 32004 KB Output is correct
2 Correct 17 ms 31952 KB Output is correct
3 Correct 17 ms 32096 KB Output is correct
4 Correct 19 ms 32080 KB Output is correct
5 Correct 18 ms 31984 KB Output is correct
6 Correct 17 ms 32036 KB Output is correct
7 Correct 19 ms 32044 KB Output is correct
8 Correct 19 ms 32080 KB Output is correct
9 Correct 18 ms 32064 KB Output is correct
10 Correct 18 ms 32212 KB Output is correct
11 Correct 18 ms 32208 KB Output is correct
12 Correct 18 ms 32056 KB Output is correct
13 Correct 458 ms 34820 KB Output is correct
14 Correct 784 ms 37604 KB Output is correct
15 Correct 674 ms 37704 KB Output is correct
16 Correct 1035 ms 37704 KB Output is correct
17 Correct 756 ms 34896 KB Output is correct
18 Correct 1004 ms 37700 KB Output is correct
19 Correct 1047 ms 37728 KB Output is correct
20 Correct 957 ms 37688 KB Output is correct
21 Correct 485 ms 32224 KB Output is correct
22 Correct 746 ms 32412 KB Output is correct
23 Correct 908 ms 32400 KB Output is correct
24 Correct 724 ms 32428 KB Output is correct
25 Correct 982 ms 40568 KB Output is correct
26 Correct 824 ms 40660 KB Output is correct
27 Correct 928 ms 40676 KB Output is correct
28 Correct 873 ms 40676 KB Output is correct
29 Correct 854 ms 48456 KB Output is correct
30 Correct 1029 ms 48456 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31952 KB Output is correct
2 Correct 18 ms 31952 KB Output is correct
3 Correct 18 ms 31984 KB Output is correct
4 Correct 19 ms 32092 KB Output is correct
5 Correct 20 ms 32080 KB Output is correct
6 Correct 22 ms 32092 KB Output is correct
7 Correct 22 ms 32104 KB Output is correct
8 Correct 21 ms 32084 KB Output is correct
9 Correct 19 ms 32004 KB Output is correct
10 Correct 17 ms 31952 KB Output is correct
11 Correct 17 ms 32096 KB Output is correct
12 Correct 19 ms 32080 KB Output is correct
13 Correct 18 ms 31984 KB Output is correct
14 Correct 17 ms 32036 KB Output is correct
15 Correct 19 ms 32044 KB Output is correct
16 Correct 19 ms 32080 KB Output is correct
17 Correct 18 ms 32064 KB Output is correct
18 Correct 18 ms 32212 KB Output is correct
19 Correct 18 ms 32208 KB Output is correct
20 Correct 18 ms 32056 KB Output is correct
21 Incorrect 18 ms 32080 KB 1st lines differ - on the 1st token, expected: '759476520', found: '966416300'
22 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31952 KB Output is correct
2 Correct 18 ms 31952 KB Output is correct
3 Correct 18 ms 31984 KB Output is correct
4 Correct 19 ms 32092 KB Output is correct
5 Correct 20 ms 32080 KB Output is correct
6 Correct 22 ms 32092 KB Output is correct
7 Correct 22 ms 32104 KB Output is correct
8 Correct 21 ms 32084 KB Output is correct
9 Correct 19 ms 32004 KB Output is correct
10 Correct 17 ms 31952 KB Output is correct
11 Correct 17 ms 32096 KB Output is correct
12 Correct 19 ms 32080 KB Output is correct
13 Correct 18 ms 31984 KB Output is correct
14 Correct 17 ms 32036 KB Output is correct
15 Correct 19 ms 32044 KB Output is correct
16 Correct 19 ms 32080 KB Output is correct
17 Correct 18 ms 32064 KB Output is correct
18 Correct 18 ms 32212 KB Output is correct
19 Correct 18 ms 32208 KB Output is correct
20 Correct 18 ms 32056 KB Output is correct
21 Incorrect 18 ms 32080 KB 1st lines differ - on the 1st token, expected: '759476520', found: '966416300'
22 Halted 0 ms 0 KB -