Submission #629956

#	Time	Username	Problem	Language	Result	Execution time	Memory
629956		jeff252	Digital Circuit (IOI22_circuit)	C++17	52 / 100	1181 ms	51680 KiB

circuit

#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],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){
    vi xd(graf[v].size()+1);
    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,q;
    cin>>n2>>m2>>q;
    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);
    while(q--){
        int l,r;
        cin>>l>>r;
        cout<<count_ways(l,r)<<"\n";
    }
}*/

Compilation message (stderr)

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

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