제출 #1080477

#제출 시각아이디문제언어결과실행 시간메모리
1080477The_Samurai디지털 회로 (IOI22_circuit)C++17
2 / 100
467 ms4668 KiB
#include "circuit.h" #include "bits/stdc++.h" using namespace std; using ll = long long; #define ff first #define ss second const int mod = 1'000'002'022; void upd(ll &a, ll b) { a = (a + b) % mod; } int n, m; vector<int> p, a, height; vector<array<ll, 2>> dp; vector<vector<int>> child; void init(int N, int M, std::vector<int> P, std::vector<int> A) { n = N, m = M, p = P, a = A; dp.assign(n + m, array<ll, 2>{}); child.assign(n, {}); height.assign(n + m, 0); for (int i = 0; i < m; i++) dp[i + n][a[i]] = 1; for (int i = 1; i < n + m; i++) { child[p[i]].emplace_back(i); height[i] = height[p[i]] + 1; } for (int u = n - 1; u >= 0; u--) { vector<ll> old(child[u].size() + 1); old[0] = 1; ll all = child[u].size(); for (int v: child[u]) { vector<ll> nw(child[u].size() + 1); all = all * (dp[v][0] + dp[v][1]) % mod; for (int i = 0; i < child[u].size(); i++) { upd(nw[i], old[i] * dp[v][0]); upd(nw[i + 1], old[i] * dp[v][1]); } old = nw; } for (int i = 1; i <= child[u].size(); i++) { upd(dp[u][1], old[i] * i); } dp[u][0] = (all - dp[u][1] + mod) % mod; } } int count_ways(int L, int R) { priority_queue<pair<int, int>> pq; set<int> vis; for (int i = L; i <= R; i++) { a[i] = !a[i]; swap(dp[i][0], dp[i][1]); if (vis.count(p[i])) continue; pq.emplace(height[p[i]], p[i]); vis.insert(p[i]); } while (!pq.empty()) { auto [h, u] = pq.top(); pq.pop(); // cout << '\t' << h << ' ' << u << endl; vector<ll> old(child[u].size() + 1); old[0] = 1; ll all = child[u].size(); dp[u][0] = dp[u][1] = 0; for (int v: child[u]) { vector<ll> nw(child[u].size() + 1); all = all * (dp[v][0] + dp[v][1]) % mod; for (int i = 0; i < child[u].size(); i++) { upd(nw[i], old[i] * dp[v][0]); upd(nw[i + 1], old[i] * dp[v][1]); } old = nw; } for (int i = 1; i <= child[u].size(); i++) { upd(dp[u][1], old[i] * i); } dp[u][0] = (all - dp[u][1] + mod) % mod; if (vis.count(p[u]) or u == 0) continue; vis.insert(p[u]); pq.emplace(height[p[u]], p[u]); } return dp[0][1]; }

컴파일 시 표준 에러 (stderr) 메시지

circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:36:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |             for (int i = 0; i < child[u].size(); i++) {
      |                             ~~^~~~~~~~~~~~~~~~~
circuit.cpp:42:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for (int i = 1; i <= child[u].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~
circuit.cpp: In function 'int count_ways(int, int)':
circuit.cpp:70:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |             for (int i = 0; i < child[u].size(); i++) {
      |                             ~~^~~~~~~~~~~~~~~~~
circuit.cpp:76:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for (int i = 1; i <= child[u].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...