Submission #642950

#	Time	Username	Problem	Language	Result	Execution time	Memory
642950		Pajaraja	Digital Circuit (IOI22_circuit)	C++17	2 / 100	3051 ms	7680 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
#include <vector>
#define MAXN 200007
#define MOD 1000002022
using namespace std;
vector<int> g[MAXN];
long long a[MAXN],t[MAXN],seg[2][MAXN];
int n,m,p[MAXN],st[MAXN];
void dfst(int s)
{
    for(int i=0;i<g[s].size();i++) dfst(g[s][i]);
    if(g[s].size()==0) t[s]=1;
    else t[s]=g[s].size();
    for(int i=0;i<g[s].size();i++) t[s]=(t[s]*t[g[s][i]])%MOD;
}
void dfs(int s,long long p)
{
    if(s>=n) {a[s-n]=p; return;}
    vector<long long> lv(g[s].size()+7),ds(g[s].size()+7);
    ds[0]=1; lv[g[s].size()+1]=1;
    for(int i=0;i<g[s].size();i++) ds[i+1]=(ds[i]*t[g[s][i]])%MOD;
    for(int i=g[s].size()-1;i>=0;i--) lv[i+1]=(lv[i+2]*t[g[s][i]])%MOD;
    for(int i=0;i<g[s].size();i++) dfs(g[s][i],p*((ds[i]*lv[i+2])%MOD)%MOD);

}
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++) g[P[i]].push_back(i);
    for(int i=0;i<M;i++) st[i]=A[i];
    dfst(0); dfs(0,1);
}

int count_ways(int L, int R) {
    long long sol=0;
    for(int i=L-n;i<=R-n;i++) st[i]^=1;
    for(int i=0;i<m;i++) {sol=sol+a[i]*st[i]; if(sol>MAXN) sol-=MAXN;}
    return sol;
}

Compilation message (stderr)

circuit.cpp: In function 'void dfst(int)':
circuit.cpp:12:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i=0;i<g[s].size();i++) dfst(g[s][i]);
      |                 ~^~~~~~~~~~~~
circuit.cpp:15:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int i=0;i<g[s].size();i++) t[s]=(t[s]*t[g[s][i]])%MOD;
      |                 ~^~~~~~~~~~~~
circuit.cpp: In function 'void dfs(int, long long int)':
circuit.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=0;i<g[s].size();i++) ds[i+1]=(ds[i]*t[g[s][i]])%MOD;
      |                 ~^~~~~~~~~~~~
circuit.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i=0;i<g[s].size();i++) dfs(g[s][i],p*((ds[i]*lv[i+2])%MOD)%MOD);
      |                 ~^~~~~~~~~~~~

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