oj.uz

Submission #642950

# Submission time Handle Problem Language Result Execution time Memory
642950 2022-09-20T23:45:42 Z Pajaraja Digital Circuit (IOI22_circuit) C++17
2 / 100
 3000 ms 7680 KB 
#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

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 5072 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 3 ms 5036 KB Output is correct
7 Correct 3 ms 5072 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 2 ms 4944 KB Output is correct
2 Incorrect 3 ms 4944 KB 1st lines differ - on the 1st token, expected: '52130940', found: '-1833336505'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 5072 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 3 ms 5036 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 3 ms 5072 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Incorrect 3 ms 4944 KB 1st lines differ - on the 1st token, expected: '52130940', found: '-1833336505'
11 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3051 ms 7680 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3051 ms 7680 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 5072 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 3 ms 5036 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 3 ms 5072 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Incorrect 3 ms 4944 KB 1st lines differ - on the 1st token, expected: '52130940', found: '-1833336505'
11 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 5072 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 3 ms 5036 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 3 ms 5072 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Incorrect 3 ms 4944 KB 1st lines differ - on the 1st token, expected: '52130940', found: '-1833336505'
11 Halted 0 ms 0 KB -