Submission #1195628

#TimeUsernameProblemLanguageResultExecution timeMemory
1195628agrim_09September (APIO24_september)C++20
75 / 100
1095 ms7924 KiB
#include "september.h" #include <bits/stdc++.h> using namespace std; int solve(int n, int m, vector<int>par, vector<vector<int>>obs) { for(int i = 0;i<m;i++){ obs[i].push_back(0); } vector<bool>to_check(n,false); vector<set<int>>sets(m); for(int i = 0;i<n-1;i++){ for(int j = 0;j<m;j++){ sets[j].insert(obs[j][i]); } bool yes = true; for(int j = 0;j<m-1;j++){ if(sets[j]!=sets[j+1]){ yes = false; break; } } to_check[i] = yes; } // solving for m = 1 vector<bool>in_stack(n,false); vector<int>to_take(n); for(int i = 1;i<n;i++){ to_take[par[i]]++; } vector<bool>is_fine(n,false); vector<int>vec = obs[0]; int stack_size = 0; for(int i = 0;i<n-1;i++){ int u = vec[i]; in_stack[u] = true; stack_size++; if(to_take[u]==0){ stack_size--; in_stack[u] = false; if(par[u]!=-1){ to_take[par[u]]--; if(to_take[par[u]]==0 and in_stack[par[u]]){ stack_size--; in_stack[par[u]] = false; } } } else{ if(par[u]!=-1){ to_take[par[u]]--; if(to_take[par[u]]==0 and in_stack[par[u]]){ stack_size--; in_stack[par[u]] = false; } } } if(stack_size==0){ is_fine[i] = true; } } int ans = 0; for(int i = 0;i<n-1;i++){ ans += (to_check[i]&&is_fine[i]); } 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...