Submission #1226716

#TimeUsernameProblemLanguageResultExecution timeMemory
1226716SpyrosAlivSeptember (APIO24_september)C++20
100 / 100
102 ms7360 KiB
#include "september.h" #include <bits/stdc++.h> using namespace std; int n, m; vector<int> par; int solve(int N, int M, vector<int> F, vector<std::vector<int>> S) { n = N; m = M; par = F; vector<int> early(n, n), late(n, 0); for (int i = 0; i < m; i++) { for (int j = 0; j < n-1; j++) { early[S[i][j]] = min(early[S[i][j]], j); late[S[i][j]] = max(late[S[i][j]], j); } } vector<int> maxR(n, 0); for (int i = 1; i < n; i++) { maxR[early[i]] = max(maxR[early[i]], late[i]); } vector<int> cnt(n, 0); vector<bool> inside(n, false); for (int i = 1; i < n; i++) cnt[par[i]]++; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; int tot = 0; set<int> proc; int maxEnd = 0; for (int i = 0; i < n - 1; i++) { maxEnd = max(maxEnd, maxR[i]); for (int j = 0; j < m; j++) { proc.insert(S[j][i]); } if (maxEnd != i) continue; for (auto x: proc) { pq.push({cnt[x], x}); inside[x] = true; while (!pq.empty()) { if (cnt[pq.top().second] != pq.top().first) { pq.pop(); continue; } int curr = pq.top().second; if (cnt[curr] == 0) { pq.pop(); cnt[par[curr]]--; if (inside[par[curr]]) pq.push({cnt[par[curr]], par[curr]}); continue; } break; } } if (pq.empty()) tot++; proc.clear(); } return tot; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...