Submission #1068701

#TimeUsernameProblemLanguageResultExecution timeMemory
1068701beaconmcDigital Circuit (IOI22_circuit)C++17
2 / 100
449 ms16216 KiB
#include <bits/stdc++.h> typedef int ll; using namespace std; #define FOR(i, x, y) for(ll i=x; i<y; i++) #define FORNEG(i, x, y) for(ll i=x; i>y; i--) #define fast() ios_base::sync_with_stdio(false);cin.tie(NULL) basic_string<ll> edges[200001]; ll possible[200001]; ll contrib[200001]; ll dps[200001]; vector<int> p; int initdfs(ll a){ if (edges[a].size() == 0) return possible[a] = 1; ll temp = 1; for (auto&i : edges[a]){ temp *= initdfs(i); temp %= 1000002022; } temp *= edges[a].size(); temp %= 1000002022; return possible[a] = temp; } int dp(ll a){ if (a==0) return 1; if (dps[a] != -1) return dps[a]; ll temp = 1; for (auto&i : edges[p[a]]){ if (i != a) temp *= possible[i]; temp %= 1000002022; } dps[a] = temp * dp(p[a]) % 1000002022; return dps[a]; } ll n,m; const ll NN = (1<<18); ll tree[NN*2]; ll actual[NN*2]; ll lazy[NN*2]; int actupd(ll a, ll b, ll val, ll k=1, ll x = 0, ll y = NN-1){ if (b<x || a>y) return actual[k]; if (a<=x && y<=b){ actual[k] += val; actual[k] %= 1000002022; return actual[k]; } ll mid = (x+y)/2; actual[k] = actupd(a,b,val,k*2, x, mid) + actupd(a,b,val,k*2+1, mid+1, y); actual[k] %= 1000002022; return actual[k]; } void prop(ll k){ lazy[k*2] += lazy[k]; lazy[k*2+1] += lazy[k]; if (lazy[k] %2==1){ tree[k] = (actual[k] - tree[k]+1000002022)%1000002022; } lazy[k] = 0; } int upd(ll a, ll b, ll k=1, ll x = 0, ll y = NN-1){ if (b<x || a>y) return lazy[k]%2==0 ? tree[k] : ((actual[k] - tree[k]+1000002022)%1000002022); if (a<=x && y<=b){ lazy[k] += 1; return lazy[k]%2==0 ? tree[k] : ((actual[k] - tree[k]+1000002022)%1000002022); } ll mid = (x+y)/2; prop(k); tree[k] = upd(a,b,k*2, x, mid) + upd(a,b,k*2+1, mid+1, y); tree[k] %= 1000002022; return lazy[k]%2==0 ? tree[k] : ((actual[k] - tree[k]+1000002022)%1000002022); } void init(int N, int M, std::vector<int> P, std::vector<int> A) { FOR(i,0,200001) dps[i] = -1; FOR(i,0,NN*2) tree[i] = 0, actual[i] = 0, lazy[i] = 0; p = P; n = N; m = M; FOR(i,1,N+M){ edges[P[i]].push_back(i); } initdfs(0); FOR(i,N,N+M){ ll temp = possible[i]; temp *= dp(i); contrib[i] = temp%1000002022; } FOR(i,n,n+m){ actupd(i-n+1, i-n+1, contrib[i]); } FOR(i,0,NN*2) tree[i] = actual[i]; FOR(i,n,n+m){ if (A[i-n] == 0){ upd(i-n+1, i-n+1); } } } int count_ways(int L, int R) { upd(L-n+1, R-n+1); return lazy[1]%2==0 ? tree[1] : ((actual[1] - tree[1]+1000002022)%1000002022); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...