# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1078492 | allin27x | Digital Circuit (IOI22_circuit) | C++17 | 467 ms | 12376 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>
using namespace std;
#define int long long
const int mod = 1000002022;
const int MAXN = 100007;
int ar[MAXN];
int n,m;
vector<int> ch[2*MAXN];
int mlt[2*MAXN];
int sgt[4*MAXN];
int rel[MAXN];
int res = 0;
void update(int i, int v) {
for (sgt[i+=2*MAXN]=v; i>1; i>>=1) sgt[i>>1] = (sgt[i] * sgt[i^1]) % mod;
}
int query(int l, int r) {
int res = 1;
for (l+=2*MAXN, r+=2*MAXN+1; l<r; l>>=1, r>>=1) {
if (l&1) res *= sgt[l++], res %= mod;
if (r&1) res *= sgt[--r], res %= mod;
}
return res;
}
int dfs0(int i) {
vector<int> vl;
for (int c: ch[i]) vl.push_back(dfs0(c));
if (vl.size() == 0) return 1;
int ans = vl.size(); for (int i=0; i<vl.size(); i++) ans *= vl[i], ans%=mod;
for (int i=0; i<vl.size(); i++) update(i, vl[i]);
for (int j=0; j<vl.size(); j++) {
mlt[ch[i][j]] = ((query(0, j-1)) * query(j+1, vl.size()-1)) % mod;
}
return ans;
}
void dfs1(int i, int p) {
if (ch[i].size() == 0) {
rel[i-n] = (p*mlt[i]) % mod;
} else {
for (int c: ch[i]) {
dfs1(c, (p*mlt[i]) % mod);
}
}
}
int pr[MAXN];
int t[4*MAXN];
int lz[4*MAXN];
int sum(int l, int r) {
if (!l) return pr[r];
return pr[r] - pr[l-1];
}
void init(signed N, signed M, std::vector<signed> P, std::vector<signed> A) {
for (int i=0; i<M; i++) ar[i] = A[i]; n= N;m=M;
for (int i=1; i<M+N; i++) ch[P[i]].push_back(i);
for (int i=0; i<4*MAXN; i++) sgt[i] = 1;
for (int i=0; i<2*MAXN; i++) mlt[i] = 1;
dfs0(0); dfs1(0,1);
pr[0] = rel[0]; for (int i=1; i<M; i++) pr[i] = pr[i-1] + rel[i];
}
signed count_ways(signed L, signed R) {
L-=n; R-=n;
return 1;
}
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... |