Submission #1158269

#TimeUsernameProblemLanguageResultExecution timeMemory
1158269countlessSeptember (APIO24_september)C++20
0 / 100
0 ms328 KiB
#include "september.h" #include <bits/stdc++.h> #include <vector> using namespace std; int dfs(int node, vector<vector<int>> &down, vector<bool> &vis) { int res = 0; for (auto child : down[node]) { if (!vis[child]) { vis[child] = true; res++; res += dfs(child, down, vis); } } return res; } int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) { int ans = 0; vector<vector<int>> down(N, vector<int>()); for (int i = 1; i < N; i++) down[F[i]].push_back(i); int dels = 0; int sweep = 0; vector<bool> vis(N, false); vector<int> cnt(N, 0); for (int i = 0; i < N; i++) { for (int m = 0; m < M; m++) { // delete itself and all its children // not including vis'd if (!vis[S[m][i]]) { vis[S[m][i]] = true; dels++; dels += dfs(S[m][i], down, vis); } // increment how many times we've seen this node cnt[S[m][i]]++; // interval start and end // first time we've seen it if (cnt[S[m][i]] == 1) sweep++; // last time we've seen it if (cnt[S[m][i]] == M) sweep--; } // when an interval "closes," increment ans // an interval closes when // we've seen all the nodes in the interval // specifically, for any node, it's subtree is contained in the interval // thus, this is only possible when the amount of deletions // is equal to the amount of nodes in the interval if (i + 1 == dels && sweep == 0) { ans++; } } return ans; }
#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...