# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
995527 | 2024-06-09T09:22:17 Z | mindiyak | September (APIO24_september) | C++17 | 1 ms | 348 KB |
#include "september.h" #include <vector> #include <iostream> #include <set> using namespace std; vector<vector<int>> sons; vector<int> flagged; vector<int> removed; vector<int> parent; set<int> to_be_removed; bool check_sons(int pos){ bool a = true; for(int i=0;i<sons[pos].size();i++){ if(removed[sons[pos][i]] == 0){ a = false; to_be_removed.insert(sons[pos][i]); // cout << "to_be_removed - add - " << sons[pos][i] << endl; } } return a; } void remove_parents(int pos){ if(flagged[parent[pos]] == 0)return; if(check_sons(parent[pos])){ removed[parent[pos]] = 1; // cout << "to_be_removed - remove - " << parent[pos] << endl; if(to_be_removed.count(parent[pos])){ to_be_removed.erase(parent[pos]); } remove_parents(parent[pos]); } } int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) { sons.resize(N,vector<int>()); removed.resize(N,0); flagged.resize(N,0); parent.resize(N,0); to_be_removed.clear(); for(int i=1;i<N;i++){ sons[F[i]].push_back(i); parent[i] = F[i]; } int ans = 0; for(int i=0;i<N-1;i++){ bool check = check_sons(S[0][i]); // cout << "to_be_removed - remove - " << S[0][i] << endl; if(to_be_removed.count(S[0][i])){ to_be_removed.erase(S[0][i]); } // for (auto it = to_be_removed.begin(); it !=to_be_removed.end(); ++it) // cout << ' ' << *it; // cout << endl; // cout << S[0][i] << " " << check << " " << to_be_removed.empty() << endl; if(check){ removed[S[0][i]] = 1; remove_parents(S[0][i]); if(to_be_removed.empty()){ ans ++; } }else{ flagged[S[0][i]] = 1; } // for(int j=0;j<N;j++)cout<<removed[j] << " "; // cout << endl; // for(int j=0;j<N;j++)cout<<flagged[j] << " "; // cout << endl; } return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Incorrect | 0 ms | 348 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Incorrect | 0 ms | 348 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 344 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Incorrect | 0 ms | 348 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 344 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Incorrect | 0 ms | 348 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 344 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Incorrect | 0 ms | 348 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 344 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Incorrect | 0 ms | 348 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |