Submission #1057594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057594		boyliguanhan	Digital Circuit (IOI22_circuit)	C++17	100 / 100	684 ms	65692 KiB

circuit

#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<ll>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]) CC++,
    dfs2(i,K*v1[CC-1]%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 (stderr)

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<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   for(int i=1;i<v1.size();i++)
      |               ~^~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 4 / 4
• Subtask 5: 12 / 12
• Subtask 6: 27 / 27
• Subtask 7: 28 / 28
• Subtask 8: 11 / 11