oj.uz

Submission #1057590

# Submission time Handle Problem Language Result Execution time Memory
1057590 2024-08-13T22:37:28 Z vjudge1 Digital Circuit (IOI22_circuit) C++17
52 / 100
 689 ms 61008 KB 
#include "circuit.h"
#include <vector>
typedef long long ll;
using namespace std;
const ll mod=1e9+2022;
struct segtree{
  struct DATA{
    ll totsum,actsum;
    int lz;
    DATA(){
      totsum=actsum=lz=0;
    }
    DATA(ll v){
      totsum=actsum=v;
      lz=0;
    }
    void apply(){
      lz^=1;
    }
    void flip(){
      lz^=1;
      actsum=(totsum+mod-actsum)%mod;
    }
    DATA(DATA a,DATA b){
      totsum=a.totsum+b.totsum;
      lz=0;actsum=a.actsum+b.actsum;
      totsum%=mod,actsum%=mod;
    }
  } T[1<<20];
  void pd(int i){
      if(T[i].lz)
        T[i].flip(),
        T[i*2].apply(),
        T[i*2+1].apply();
  }
  void init(int i,int l,int r,ll arr[]){
    if(l==r) return void(T[i]=DATA(arr[l]));
    init(i*2,l,l+r>>1,arr);
    init(i*2+1,l+r+2>>1,r,arr);
    T[i]=DATA(T[i*2],T[i*2+1]);
  }
  void tog(int i,int l,int r,int ll,int rr){
    pd(i); if(ll<=l&&r<=rr)
      return T[i].apply(),pd(i);
    if(ll>r||l>rr) return;
    tog(i*2,l,l+r>>1,ll,rr);
    tog(i*2+1,l+r+2>>1,r,ll,rr);
    T[i]=DATA(T[i*2],T[i*2+1]);
  }
} ST;
vector<int>adj[200100];
ll PRD[200100],FINALE[200100];
void dfs1(int n){
  if(adj[n].empty())
    return void(PRD[n]=1);
  PRD[n]=adj[n].size();
  for(auto x:adj[n])
    dfs1(x),PRD[n]=PRD[n]*PRD[x]%mod;
}
void dfs2(int n,ll K){
  if(adj[n].empty()){
    FINALE[n]=K;
  }
  vector<int>v1,v2;
  v1.push_back(1);
  for(auto i:adj[n])
    v1.push_back(PRD[i]),
    v2.push_back(PRD[i]);
  v2.push_back(1);
  for(int i=1;i<v1.size();i++)
    v1[i]=v1[i-1]*v1[i]%mod;
  for(int i=v1.size();--i;)
    v2[i-1]=v2[i-1]*v2[i]%mod;
  int CC=0;
  for(auto i:adj[n])
    dfs2(i,K*v1[CC++]%mod*v2[CC]%mod);
}
int N,M;
void init(int N_, int M_, std::vector<int> P, std::vector<int> A) {
  N=N_,M=M_;
  for(int i=1;i<N+M;i++)
    adj[P[i]].push_back(i);
  dfs1(0);dfs2(0,1);
  ST.init(1,N,N+M-1,FINALE);
  for(int i=0;i<M;i++)
    if(!A[i])
      ST.tog(1,0,M-1,i,i);
}

int count_ways(int L, int R) {
  ST.tog(1,N,N+M-1,L,R);
  return ST.T[1].actsum;
}

Compilation message

circuit.cpp: In member function 'void segtree::init(int, int, int, ll*)':
circuit.cpp:38:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     init(i*2,l,l+r>>1,arr);
      |                ~^~
circuit.cpp:39:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |     init(i*2+1,l+r+2>>1,r,arr);
      |                ~~~^~
circuit.cpp: In member function 'void segtree::tog(int, int, int, int, int)':
circuit.cpp:46:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |     tog(i*2,l,l+r>>1,ll,rr);
      |               ~^~
circuit.cpp:47:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |     tog(i*2+1,l+r+2>>1,r,ll,rr);
      |               ~~~^~
circuit.cpp: In function 'void dfs2(int, ll)':
circuit.cpp:70:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   for(int i=1;i<v1.size();i++)
      |               ~^~~~~~~~~~
circuit.cpp:76:19: warning: operation on 'CC' may be undefined [-Wsequence-point]
   76 |     dfs2(i,K*v1[CC++]%mod*v2[CC]%mod);
      |                 ~~^~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 31832 KB Output is correct
2 Correct 4 ms 31832 KB Output is correct
3 Correct 4 ms 31832 KB Output is correct
4 Correct 4 ms 31832 KB Output is correct
5 Correct 3 ms 31852 KB Output is correct
6 Correct 4 ms 31856 KB Output is correct
7 Correct 3 ms 31832 KB Output is correct
8 Correct 3 ms 31892 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31832 KB Output is correct
2 Correct 3 ms 31832 KB Output is correct
3 Correct 4 ms 31700 KB Output is correct
4 Correct 3 ms 31656 KB Output is correct
5 Correct 3 ms 31832 KB Output is correct
6 Correct 3 ms 31688 KB Output is correct
7 Correct 4 ms 31832 KB Output is correct
8 Correct 3 ms 31832 KB Output is correct
9 Correct 4 ms 31928 KB Output is correct
10 Correct 4 ms 31936 KB Output is correct
11 Correct 4 ms 32088 KB Output is correct
12 Correct 4 ms 31860 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 31832 KB Output is correct
2 Correct 4 ms 31832 KB Output is correct
3 Correct 4 ms 31832 KB Output is correct
4 Correct 4 ms 31832 KB Output is correct
5 Correct 3 ms 31852 KB Output is correct
6 Correct 4 ms 31856 KB Output is correct
7 Correct 3 ms 31832 KB Output is correct
8 Correct 3 ms 31892 KB Output is correct
9 Correct 4 ms 31832 KB Output is correct
10 Correct 3 ms 31832 KB Output is correct
11 Correct 4 ms 31700 KB Output is correct
12 Correct 3 ms 31656 KB Output is correct
13 Correct 3 ms 31832 KB Output is correct
14 Correct 3 ms 31688 KB Output is correct
15 Correct 4 ms 31832 KB Output is correct
16 Correct 3 ms 31832 KB Output is correct
17 Correct 4 ms 31928 KB Output is correct
18 Correct 4 ms 31936 KB Output is correct
19 Correct 4 ms 32088 KB Output is correct
20 Correct 4 ms 31860 KB Output is correct
21 Incorrect 4 ms 31832 KB 1st lines differ - on the 1st token, expected: '759476520', found: '110486194'
22 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 33880 KB Output is correct
2 Correct 527 ms 35928 KB Output is correct
3 Correct 560 ms 35952 KB Output is correct
4 Correct 567 ms 35928 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 33880 KB Output is correct
2 Correct 527 ms 35928 KB Output is correct
3 Correct 560 ms 35952 KB Output is correct
4 Correct 567 ms 35928 KB Output is correct
5 Correct 478 ms 33872 KB Output is correct
6 Correct 579 ms 35928 KB Output is correct
7 Correct 619 ms 35920 KB Output is correct
8 Correct 609 ms 35928 KB Output is correct
9 Correct 287 ms 31832 KB Output is correct
10 Correct 535 ms 32088 KB Output is correct
11 Correct 569 ms 32088 KB Output is correct
12 Correct 551 ms 32088 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31832 KB Output is correct
2 Correct 3 ms 31832 KB Output is correct
3 Correct 4 ms 31700 KB Output is correct
4 Correct 3 ms 31656 KB Output is correct
5 Correct 3 ms 31832 KB Output is correct
6 Correct 3 ms 31688 KB Output is correct
7 Correct 4 ms 31832 KB Output is correct
8 Correct 3 ms 31832 KB Output is correct
9 Correct 4 ms 31928 KB Output is correct
10 Correct 4 ms 31936 KB Output is correct
11 Correct 4 ms 32088 KB Output is correct
12 Correct 4 ms 31860 KB Output is correct
13 Correct 435 ms 33880 KB Output is correct
14 Correct 527 ms 35928 KB Output is correct
15 Correct 560 ms 35952 KB Output is correct
16 Correct 567 ms 35928 KB Output is correct
17 Correct 478 ms 33872 KB Output is correct
18 Correct 579 ms 35928 KB Output is correct
19 Correct 619 ms 35920 KB Output is correct
20 Correct 609 ms 35928 KB Output is correct
21 Correct 287 ms 31832 KB Output is correct
22 Correct 535 ms 32088 KB Output is correct
23 Correct 569 ms 32088 KB Output is correct
24 Correct 551 ms 32088 KB Output is correct
25 Correct 614 ms 37456 KB Output is correct
26 Correct 653 ms 37456 KB Output is correct
27 Correct 615 ms 37456 KB Output is correct
28 Correct 519 ms 37456 KB Output is correct
29 Correct 689 ms 61008 KB Output is correct
30 Correct 559 ms 60800 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 31832 KB Output is correct
2 Correct 4 ms 31832 KB Output is correct
3 Correct 4 ms 31832 KB Output is correct
4 Correct 4 ms 31832 KB Output is correct
5 Correct 3 ms 31852 KB Output is correct
6 Correct 4 ms 31856 KB Output is correct
7 Correct 3 ms 31832 KB Output is correct
8 Correct 3 ms 31892 KB Output is correct
9 Correct 4 ms 31832 KB Output is correct
10 Correct 3 ms 31832 KB Output is correct
11 Correct 4 ms 31700 KB Output is correct
12 Correct 3 ms 31656 KB Output is correct
13 Correct 3 ms 31832 KB Output is correct
14 Correct 3 ms 31688 KB Output is correct
15 Correct 4 ms 31832 KB Output is correct
16 Correct 3 ms 31832 KB Output is correct
17 Correct 4 ms 31928 KB Output is correct
18 Correct 4 ms 31936 KB Output is correct
19 Correct 4 ms 32088 KB Output is correct
20 Correct 4 ms 31860 KB Output is correct
21 Incorrect 4 ms 31832 KB 1st lines differ - on the 1st token, expected: '759476520', found: '110486194'
22 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 31832 KB Output is correct
2 Correct 4 ms 31832 KB Output is correct
3 Correct 4 ms 31832 KB Output is correct
4 Correct 4 ms 31832 KB Output is correct
5 Correct 3 ms 31852 KB Output is correct
6 Correct 4 ms 31856 KB Output is correct
7 Correct 3 ms 31832 KB Output is correct
8 Correct 3 ms 31892 KB Output is correct
9 Correct 4 ms 31832 KB Output is correct
10 Correct 3 ms 31832 KB Output is correct
11 Correct 4 ms 31700 KB Output is correct
12 Correct 3 ms 31656 KB Output is correct
13 Correct 3 ms 31832 KB Output is correct
14 Correct 3 ms 31688 KB Output is correct
15 Correct 4 ms 31832 KB Output is correct
16 Correct 3 ms 31832 KB Output is correct
17 Correct 4 ms 31928 KB Output is correct
18 Correct 4 ms 31936 KB Output is correct
19 Correct 4 ms 32088 KB Output is correct
20 Correct 4 ms 31860 KB Output is correct
21 Incorrect 4 ms 31832 KB 1st lines differ - on the 1st token, expected: '759476520', found: '110486194'
22 Halted 0 ms 0 KB -