#include "circuit.h"
#include <vector>
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const ll mod = 1e9 + 2022;
const int nmax = 1e6 + 1;
vector <vector <int> > g(nmax);
vector <int> lazy(nmax);
vector <ll>t(4 * nmax), t1(4 * nmax);
/*
3 4 3
-1 0 1 2 1 1 0
1 0 1 0
3 4
4 5
3 6
*/
void push(int v){
if(!lazy[v]) return;
lazy[2 * v] ^= lazy[v];
lazy[2 * v + 1] ^= lazy[v];
swap(t[2 * v], t1[2 * v]);
swap(t[2 * v + 1], t1[2 * v + 1]);
lazy[v] = 0;
}
void update(int v, int l, int r, int st, int fin){
if(l > fin || r < st) return;
if(l >= st && r <= fin){
swap(t[v], t1[v]);
lazy[v] ^= 1;
return;
}
int m = (l + r) / 2;
push(v);
update(2 * v, l, m, st, fin);
update(2 * v + 1, m + 1, r, st, fin);
t[v] = t[2 * v] + t[2 * v + 1]; t[v] %= mod;
t1[v] = t1[2 * v] + t1[2 * v + 1]; t1[v] %= mod;
}
vector <int> a;
vector <ll> val(nmax);
int n;
void build(int v, int l, int r){
if(l == r){
if(a[l - 1]){
t[v] = val[l + n];
return;
}
else t1[v] = val[l + n];
return;
}
int m = (l + r) / 2;
build(2 * v, l, m);
build(2 * v + 1, m + 1, r);
t[v] = t[2 * v] + t[2 * v + 1]; t[v] %= mod;
t1[v] = t1[2 * v] + t1[2 * v + 1]; t1[v] %= mod;
}
vector <ll> dp(nmax);
void dfs(int v){
dp[v] = max((int)g[v].size(), 1);
for(int to : g[v]){
dfs(to);
dp[v] *= dp[to];
dp[v] %= mod;
}
}
void DFS(int v, ll value = 1){
vector <ll> pref, suf;
pref.resize(g[v].size());
suf.resize(g[v].size());
for(int i = 0; i < g[v].size(); i++){
if(i == 0) pref[i] = dp[g[v][i]];
else pref[i] = dp[g[v][i]] * pref[i - 1] % mod;
}
for(int i = g[v].size() - 1; i >= 0; i--){
if(i == g[v].size() - 1){
suf[i] = dp[g[v][i]];
}
else suf[i] = suf[i + 1] * dp[g[v][i]] % mod;
}
for(int i = 0; i < g[v].size(); i++){
val[g[v][i]] = 1;
int u = g[v][i];
if(i) val[u] *= pref[i - 1], val[u] %= mod;
if(i != g[v].size() - 1)
val[u] *= suf[i + 1], val[u] %= mod;
DFS(u, val[u]);
}
}
int m;
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n = N;
m = M;
a = A;
for(int i = 0; i < n + m; i++){
int x = P[i];
if(x != -1)
g[x + 1].pb(i + 1);
}
dfs(1);
DFS(1);
/*for(int i = 1; i <= n + m; i++){
cout << dp[i] << ' ';
}
cout << "\n";
for(int i = 1; i <= m; i++) cout << val[i + n] << ' ';*/
build(1, 1, m);
cout << t[1] << ' ';
}
int count_ways(int L, int R) {
update(1, 1, m, L - n + 1, R - n + 1);
return t[1];
}
Compilation message
circuit.cpp: In function 'void DFS(int, long long int)':
circuit.cpp:87:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for(int i = 0; i < g[v].size(); i++){
| ~~^~~~~~~~~~~~~
circuit.cpp:92:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | if(i == g[v].size() - 1){
| ~~^~~~~~~~~~~~~~~~~~
circuit.cpp:97:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int i = 0; i < g[v].size(); i++){
| ~~^~~~~~~~~~~~~
circuit.cpp:101:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | if(i != g[v].size() - 1)
| ~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
105916 KB |
Possible tampering with the output or unexpected termination of the program |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
105896 KB |
Possible tampering with the output or unexpected termination of the program |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
105916 KB |
Possible tampering with the output or unexpected termination of the program |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
107912 KB |
Possible tampering with the output or unexpected termination of the program |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
107912 KB |
Possible tampering with the output or unexpected termination of the program |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
105896 KB |
Possible tampering with the output or unexpected termination of the program |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
105916 KB |
Possible tampering with the output or unexpected termination of the program |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
105916 KB |
Possible tampering with the output or unexpected termination of the program |
| 2 |
Halted |
0 ms |
0 KB |
- |
