Submission #1074299

#TimeUsernameProblemLanguageResultExecution timeMemory
1074299ZicrusDigital Circuit (IOI22_circuit)C++17
11 / 100
3021 ms7536 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 numOff = 0, numOn = 0; for (ll mask = 0; mask < (1ll << adj[i].size()); mask++) { ll valOff = adj[i].size() - __builtin_popcount(mask); ll valOn = __builtin_popcount(mask); for (int b = 0; b < adj[i].size(); b++) { valOff *= getDp((mask >> b) & 1, adj[i][b]); valOn *= getDp((mask >> b) & 1, adj[i][b]); valOff %= 1000002022; valOn %= 1000002022; } numOff += valOff; numOn += valOn; numOff %= 1000002022; numOn %= 1000002022; } dp[0][i] = numOff; dp[1][i] = numOn; } 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:22:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for (int b = 0; b < adj[i].size(); b++) {
      |                         ~~^~~~~~~~~~~~~~~
#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...