Submission #945044

#TimeUsernameProblemLanguageResultExecution timeMemory
945044abczzDigital Circuit (IOI22_circuit)C++17
100 / 100
709 ms40000 KiB
#include "circuit.h" #include <iostream> #include <vector> #include <array> #define ll long long using namespace std; vector <ll> adj[200000]; bool B[200000]; array<ll, 2> st[400000]; bool lazy[400000]; ll n, m, sz[200000], X[200000], M = 1e9 + 2022; void dfs(ll u) { sz[u] = adj[u].size(); for (auto v : adj[u]) { dfs(v); sz[u] *= sz[v]; sz[u] %= M; } if (!sz[u]) sz[u] = 1; } void solve(ll u, ll w) { X[u] = w; vector <ll> pref, suf; pref.resize(adj[u].size()); suf.resize(adj[u].size()); for (int i=0; i<adj[u].size(); ++i) { pref[i] = sz[adj[u][i]]; if (i) { pref[i] *= pref[i-1]; pref[i] %= M; } } for (int i=adj[u].size()-1; i>=0; --i) { suf[i] = sz[adj[u][i]]; if (i != adj[u].size()-1) { suf[i] *= suf[i+1]; suf[i] %= M; } } for (int i=0; i<adj[u].size(); ++i) { solve(adj[u][i], (w * (((i ? pref[i-1] : 1) * (i != adj[u].size()-1 ? suf[i+1] : 1)) % M))%M); } } void build(ll id, ll l, ll r) { if (l == r) { st[id] = {X[l], 0}; if (B[l]) swap(st[id][0], st[id][1]); return; } ll mid = (l+r)/2; build(id*2, l, mid); build(id*2+1, mid+1, r); st[id][0] = st[id*2][0] + st[id*2+1][0]; st[id][1] = st[id*2][1] + st[id*2+1][1]; st[id][0] %= M; st[id][1] %= M; } void push(ll id) { if (lazy[id]) { lazy[id*2] ^= 1; lazy[id*2+1] ^= 1; swap(st[id*2][0], st[id*2][1]); swap(st[id*2+1][0], st[id*2+1][1]); lazy[id] = 0; } } void update(ll id, ll l, ll r, ll ql, ll qr) { if (qr < l || r < ql) return; else if (ql <= l && r <= qr) { lazy[id] ^= 1; swap(st[id][0], st[id][1]); return; } ll mid = (l+r)/2; push(id); update(id*2, l, mid, ql, qr); update(id*2+1, mid+1, r, ql, qr); st[id][0] = st[id*2][0] + st[id*2+1][0]; st[id][1] = st[id*2][1] + st[id*2+1][1]; st[id][0] %= M; st[id][1] %= M; } void init(int N, int M, std::vector<int> P, std::vector<int> A) { n = N, m = M; for (int i=N; i<N+M; ++i) { B[i] = A[i-N]; } for (int i=1; i<P.size(); ++i) { adj[P[i]].push_back(i); } dfs(0); solve(0, 1); build(1, n, n+m-1); } int count_ways(int L, int R) { update(1, n, n+m-1, L, R); return st[1][1]; }

Compilation message (stderr)

circuit.cpp: In function 'void solve(long long int, long long int)':
circuit.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   for (int i=0; i<adj[u].size(); ++i) {
      |                 ~^~~~~~~~~~~~~~
circuit.cpp:37:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     if (i != adj[u].size()-1) {
      |         ~~^~~~~~~~~~~~~~~~~~
circuit.cpp:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for (int i=0; i<adj[u].size(); ++i) {
      |                 ~^~~~~~~~~~~~~~
circuit.cpp:43:54: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     solve(adj[u][i], (w * (((i ? pref[i-1] : 1) * (i != adj[u].size()-1 ? suf[i+1] : 1)) % M))%M);
      |                                                    ~~^~~~~~~~~~~~~~~~~~
circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:94:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |   for (int i=1; i<P.size(); ++i) {
      |                 ~^~~~~~~~~
#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...