Submission #1075151

#TimeUsernameProblemLanguageResultExecution timeMemory
1075151ZicrusDigital Circuit (IOI22_circuit)C++17
22 / 100
3025 ms7620 KiB
#include <bits/stdc++.h> #include "circuit.h" using namespace std; typedef long long ll; int n, m; vector<int> p, a, mark; vector<vector<int>> adj; vector<vector<ll>> dp; ll getDp(int state, int i) { if (i >= n) return state == a[i-n]; return dp[state][i]; } void update(int i) { ll ans0 = getDp(0, adj[i][0]); ll ans1 = getDp(1, adj[i][0]); ll tmp = ans0 + ans1; ans0 %= 1000002022; ans1 %= 1000002022; tmp %= 1000002022; for (int j = 1; j < adj[i].size(); j++) { ll b0 = getDp(0, adj[i][j]); ll b1 = getDp(1, adj[i][j]); ans0 = b0 * (tmp + ans0) + b1 * ans0; ans1 = b1 * (tmp + ans1) + b0 * ans1; tmp *= b0 + b1; ans0 %= 1000002022; ans1 %= 1000002022; tmp %= 1000002022; } dp[0][i] = ans0; dp[1][i] = ans1; } void init(int N, int M, vector<int> P, vector<int> A) { n = N, m = M; p = P; a = A; mark = vector<int>(n); adj = vector<vector<int>>(n); dp = vector<vector<ll>>(2, vector<ll>(n)); for (int i = 1; i < n+m; i++) { adj[p[i]].push_back(i); } for (int i = n-1; i >= 0; i--) { update(i); } } int count_ways(int L, int R) { L -= n; R -= n; priority_queue<int> q; for (int i = L; i <= R; i++) { a[i] = !a[i]; int cur = p[n+i]; while (cur != -1 && !mark[cur]) { mark[cur] = true; q.push({cur}); cur = p[cur]; } } while (!q.empty()) { int cur = q.top(); q.pop(); update(cur); mark[cur] = false; } return dp[1][0]; } #ifdef TEST #include "grader.cpp" #endif

Compilation message (stderr)

circuit.cpp: In function 'void update(int)':
circuit.cpp:24:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (int j = 1; j < adj[i].size(); j++) {
      |                     ~~^~~~~~~~~~~~~~~
#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...