oj.uz

Submission #710781

# Submission time Handle Problem Language Result Execution time Memory
710781 2023-03-15T19:12:00 Z ogibogi2004 Digital Circuit (IOI22_circuit) C++17
2 / 100
 606 ms 8584 KB 
#include "circuit.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+6;
const ll mod=1000002022;
ll arr[MAXN];
ll fastpow(ll x,ll p)
{
    if(p==0)return 1;
    if(p==1)return x;
    ll t=fastpow(x,p/2);
    t*=t;t%=mod;
    if(p%2==1)
    {
        t*=x;
        t%=mod;
    }
    return t;
}
struct segment_tree
{
    ll tree[4*MAXN];
    int lazy[4*MAXN];
    void build(int l,int r,int idx)
    {
        if(l==r)
        {
            tree[idx]=arr[l];
            return;
        }
        int mid=(l+r)/2;
        build(l,mid,idx*2);
        build(mid+1,r,idx*2+1);
        tree[idx]=(tree[idx*2]+tree[idx*2+1])%mod;
    }
    void push(int l,int r,int idx)
    {
        if(lazy[idx]==0)return;
        tree[idx]=mod-tree[idx];
        tree[idx]%=mod;
        if(l!=r)
        {
            lazy[idx*2]^=lazy[idx];
            lazy[idx*2+1]^=lazy[idx];
        }
        lazy[idx]=0;
    }
    void update(int idx,int l,int r,int ql,int qr)
    {
        push(l,r,idx);
        if(qr<l)return;
        if(ql>r)return;
        if(l>=ql&&r<=qr)
        {
            lazy[idx]^=1;
            push(l,r,idx);
            //cout<<"%%% "<<l<<" "<<r<<" "<<tree[idx]<<endl;
            return;
        }
        //cout<<"## "<<l<<" "<<r<<" "<<ql<<" "<<qr<<endl;
        int mid=(l+r)/2;
        update(idx*2,l,mid,ql,qr);
        update(idx*2+1,mid+1,r,ql,qr);
        tree[idx]=(tree[idx*2]+tree[idx*2+1])%mod;
        //cout<<"%%% "<<l<<" "<<r<<" "<<tree[idx]<<endl;
    }
    ll query(int l,int r,int idx,int ql,int qr)
    {
        push(l,r,idx);
        if(l>qr)return 0;
        if(r<ql)return 0;
        //cout<<"%% "<<l<<" "<<r<<" "<<tree[idx]<<endl;
        if(l>=ql&&r<=qr)return tree[idx];
        int mid=(l+r)/2;
        return (query(l,mid,idx*2,ql,qr)+query(mid+1,r,idx*2+1,ql,qr))%mod;
    }
}tr;
int m,n;
ll all_prod=1,sum1;
vector<int>g[MAXN];
ll path_prod[MAXN];
ll subtree_prod[MAXN];
void dfs_subtrees(int u)
{
    subtree_prod[u]=max(1ll,(ll)g[u].size());

    for(auto xd:g[u])
    {
        dfs_subtrees(xd);
        subtree_prod[u]*=subtree_prod[xd];
        subtree_prod[u]%=mod;
    }
}
void dfs_prods(int u)
{
    vector<ll>pref_prods;
    vector<ll>suf_prods;
    for(int i=0;i<g[u].size();i++)
    {
        if(i==0)pref_prods.push_back(max(1ll,subtree_prod[g[u][i]]));
        else
        {
            pref_prods.push_back((pref_prods.back()*max(1ll,subtree_prod[g[u][i]]))%mod);
        }
    }
    for(int i=g[u].size()-1;i>=0;i--)
    {
        if(i==g[u].size()-1)suf_prods.push_back(max(1ll,subtree_prod[g[u][i]]));
        else
        {
            suf_prods.push_back((suf_prods.back()*max(1ll,subtree_prod[g[u][i]]))%mod);
        }
    }
    reverse(suf_prods.begin(),suf_prods.end());
    for(int i=0;i<g[u].size();i++)
    {
        ll prod1=1;
        if(i>0)prod1*=pref_prods[i-1];
        if(i+1<g[u].size())prod1*=suf_prods[i+1];
        prod1%=mod;
        //cout<<u<<" -> "<<g[u][i]<<" "<<path_prod[u]<<" * "<<prod1<<endl;
        path_prod[g[u][i]]=(path_prod[u]*prod1)%mod;
        dfs_prods(g[u][i]);
    }
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    m=M;n=N;
    for(int i=1;i<N+M;i++)
    {
        g[P[i]].push_back(i);
    }
    for(int i=0;i<N;i++)
    {
        ll t=g[i].size();
        all_prod*=t;
        all_prod%=mod;
    }
    path_prod[0]=1;
    dfs_subtrees(0);
    dfs_prods(0);
    //cout<<all_prod<<endl;
    for(int i=0;i<M;i++)
    {
        //arr[i]=(all_prod*fastpow(path_prod[N+i],mod-2))%mod;
        //cout<<path_prod[N+i]<<"|"<<arr[i]<<" ";
        arr[i]=path_prod[N+i];
        //cout<<path_prod[N+i]<<" ";
        sum1+=arr[i];sum1%=mod;
        if(A[i]==0)arr[i]=mod-arr[i];
    }
    //cout<<endl;
    tr.build(0,M-1,1);
    //cout<<sum1<<" "<<tr.query(0,m-1,1,0,m-1)<<endl;
}

int count_ways(int L, int R) {
    tr.update(1,0,m-1,L-n,R-n);
    return ((sum1+tr.query(0,m-1,1,0,m-1))%mod)/2ll;
}

Compilation message

circuit.cpp: In function 'void dfs_prods(int)':
circuit.cpp:99:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for(int i=0;i<g[u].size();i++)
      |                 ~^~~~~~~~~~~~
circuit.cpp:109:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         if(i==g[u].size()-1)suf_prods.push_back(max(1ll,subtree_prod[g[u][i]]));
      |            ~^~~~~~~~~~~~~~~
circuit.cpp:116:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |     for(int i=0;i<g[u].size();i++)
      |                 ~^~~~~~~~~~~~
circuit.cpp:120:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |         if(i+1<g[u].size())prod1*=suf_prods[i+1];
      |            ~~~^~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 3 ms 5072 KB Output is correct
4 Correct 3 ms 5116 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 3 ms 5120 KB Output is correct
8 Correct 3 ms 5072 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4944 KB Output is correct
2 Incorrect 3 ms 4944 KB 2nd lines differ - on the 1st token, expected: '785285606', found: '285284595'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 3 ms 5072 KB Output is correct
4 Correct 3 ms 5116 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 3 ms 5120 KB Output is correct
8 Correct 3 ms 5072 KB Output is correct
9 Correct 4 ms 4944 KB Output is correct
10 Incorrect 3 ms 4944 KB 2nd lines differ - on the 1st token, expected: '785285606', found: '285284595'
11 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 606 ms 8584 KB 5th lines differ - on the 1st token, expected: '506785730', found: '6784719'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 606 ms 8584 KB 5th lines differ - on the 1st token, expected: '506785730', found: '6784719'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4944 KB Output is correct
2 Incorrect 3 ms 4944 KB 2nd lines differ - on the 1st token, expected: '785285606', found: '285284595'
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 3 ms 5072 KB Output is correct
4 Correct 3 ms 5116 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 3 ms 5120 KB Output is correct
8 Correct 3 ms 5072 KB Output is correct
9 Correct 4 ms 4944 KB Output is correct
10 Incorrect 3 ms 4944 KB 2nd lines differ - on the 1st token, expected: '785285606', found: '285284595'
11 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 3 ms 5072 KB Output is correct
4 Correct 3 ms 5116 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 3 ms 5120 KB Output is correct
8 Correct 3 ms 5072 KB Output is correct
9 Correct 4 ms 4944 KB Output is correct
10 Incorrect 3 ms 4944 KB 2nd lines differ - on the 1st token, expected: '785285606', found: '285284595'
11 Halted 0 ms 0 KB -