Submission #1158275

#TimeUsernameProblemLanguageResultExecution timeMemory
1158275countlessSeptember (APIO24_september)C++20
0 / 100
0 ms320 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 (const 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); // "compress" the M queries vector<int> comp(N, -1); for (int m = 0; m < M; m++) { for (int j = 0; j < N - 1; j++) { comp[S[m][j]] = max(comp[S[m][j]], j); } } int dels = 0; int sweep = 0; vector<bool> vis(N, false); vector<int> cnt(N, 0); for (int i = 0; i < N - 1; i++) { // delete itself and all its children // not including vis'd if (!vis[comp[i]]) { vis[comp[i]] = true; dels++; dels += dfs(comp[i], down, vis); } cerr << dels << endl; // increment how many times we've seen this node cnt[comp[i]]++; // interval start and end // first time we've seen it if (cnt[comp[i]] == 1) sweep++; // last time we've seen it if (cnt[comp[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...