# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
637165 | Fidan | Digital Circuit (IOI22_circuit) | C++17 | 3047 ms | 6236 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "circuit.h"
using namespace std;
typedef long long ll;
const ll mod=1000002022;
ll n, m;
vector<ll> p, a;
vector<vector<ll>> v;
vector<ll> k;
vector<ll> s;
vector<ll> pr;
void solve1(int x){
pr[x]=1;
for(ll i:v[x]) {
solve1(i);
pr[x]=(pr[x]*pr[i])%mod;
}
}
void init(int N, int M, vector<int> P, vector<int> A){
n=N;
m=M;
for(ll i=0; i<n+m; i++){
p.push_back(P[i]);
a.push_back(A[i]);
}
v.resize(n+m);
for(ll i=1; i<n+m; i++){
v[p[i]].push_back(i);
}
k.resize(n+m);
s.resize(n+m);
pr.resize(n+m);
solve1(0);
}
void solve(int x){
k[x]=0;
if(x>=n){
k[x]=a[x-n];
s[x]=0;
return;
}
for(ll i: v[x]) solve(i);
for(ll i=0; i<v[x].size(); i++){
ll l=k[v[x][i]];
for(ll j=0; j<v[x].size(); j++){
if(i!=j) l=(l*pr[v[x][j]])%mod;
}
k[x]=(k[x]+l)%mod;
}
return;
}
int count_ways(int l, int r){
if(n==1){
ll sum=0;
for(ll i=l-n; i<=r-n; i++){
a[i]=1-a[i];
}
for(ll i=0; i<m; i++){
if(a[i]==1) sum++;
}
return sum;
}
for(ll i=l-n; i<=r-n; i++){
a[i]=1-a[i];
}
solve1(0);
solve(0);
return int(k[0]);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |