oj.uz

Submission #836372

# Submission time Handle Problem Language Result Execution time Memory
836372 2023-08-24T10:41:35 Z Trumling Digital Circuit (IOI22_circuit) C++17
4 / 100
 1029 ms 12084 KB 
    #include "circuit.h"
    #include<bits/stdc++.h>
    using namespace std;
     
    #define F first
    #define S second
    #define all(x) x.begin(),x.end()
    typedef long long ll;
    #define pb push_back
    #define MOD 1000002022
     
    ll m,n;
    vector<vector<int>>g;
    vector<pair<ll,ll>> tree;
    vector<int>a;
    vector<int>dic;
    ll idx=0;
    void update(int L,int R,int p,int start)
    {
      if(L==R)
      {
        tree[start]={0,0};
        if(a[start])
        tree[start].F=1;
        else
        tree[start].S=1;
        return;
      }

      if(L<=p && p<=(L+R)/2)
      update(L,(L+R)/2,p,start*2+1);
      else
      update((L+R)/2+1,R,p,start*2+2);
      ll l=start*2+1,r=start*2+2;
      
      tree[start].F=((tree[l].F*tree[r].F)%MOD  + (tree[l].F*(tree[r].F+tree[r].S))%MOD + (tree[l].S*tree[r].F)%MOD)%MOD;
      tree[start].S=((tree[l].S*(tree[r].F+tree[r].S))%MOD + (tree[l].F*tree[r].S)%MOD + (tree[l].S*tree[r].S)%MOD)%MOD;
    }
    void build(int start)
    {
      if(g[start].size()==1)
      {
        dic[start]=idx++;
        tree[start]={0,0};
        if(a[start])
        tree[start].F=1;
        else
        tree[start].S=1;
        //cout<<start<<" |"<<tree[start].F<<' '<<tree[start].S<<'\n';
        return ;
      }
      ll l,r;
      for(auto x:g[start])
      if(x>start)
      build(x);

      ll add=0;
      if(start==0)
      add=-1;
      l=g[start][1+add];
      r=g[start][2+add];

      tree[start].F=((tree[l].F*tree[r].F)%MOD  + (tree[l].F*(tree[r].F+tree[r].S))%MOD + (tree[l].S*tree[r].F)%MOD)%MOD;
      tree[start].S=((tree[l].S*(tree[r].F+tree[r].S))%MOD + (tree[l].F*tree[r].S)%MOD + (tree[l].S*tree[r].S)%MOD)%MOD;

     // cout<<start<<" |"<<tree[start].F<<' '<<tree[start].S<<'\n';
      return ;
    }

    void init(int N, int M, vector<int> P, vector<int> A) 
    {
      n=N;
      m=M;
      tree.assign(n+m,{0,0});
      g.assign(N+M,vector<int>());
      a.assign(N+M,0);
      dic.assign(N+M,0);

      for(int i=0;i<m;i++)
      a[i+n]=A[i];

      for(int i=1;i<N+M;i++)
      {
        g[i].pb(P[i]);
        g[P[i]].pb(i);
      }
      build(0);
    }
     
    int count_ways(int L, int R) 
    {
      for(int i=L;i<=R;i++)
        a[i]=1-a[i];
      
      update(0,n,L-n,0);
      //cout<<tree[0].F<<' '<<tree[0].S;
      return tree[0].F;
    }

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 6200 KB Output is correct
2 Correct 719 ms 12076 KB Output is correct
3 Correct 639 ms 12084 KB Output is correct
4 Correct 589 ms 12064 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 6200 KB Output is correct
2 Correct 719 ms 12076 KB Output is correct
3 Correct 639 ms 12084 KB Output is correct
4 Correct 589 ms 12064 KB Output is correct
5 Incorrect 1029 ms 6184 KB 1st lines differ - on the 1st token, expected: '105182172', found: '2777846'
6 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -