Submission #1194618

#TimeUsernameProblemLanguageResultExecution timeMemory
1194618ElayV13September (APIO24_september)C++20
11 / 100
4 ms656 KiB
#include "september.h" #include <bits/stdc++.h> using namespace std; const int N = 11; const int INF = INT_MAX; vector < int > adj[N]; int dep[N] , sub[N] , idx[N] , po = 0; void dfs(int v , int p) { idx[v] = ++po; sub[v] = 1; for(int u : adj[v]){ if(u == p) continue; dep[u] = dep[v] + 1; dfs(u , v); sub[v] += sub[u]; } } void get_dep(int n , int m , vector < int > F) { for(int i = 1;i <= n - 1;i++) { adj[F[i]].push_back(i); adj[i].push_back(F[i]); } dfs(0 , -1); } void fix() { po = 0; for(int i = 0;i < N;i++) dep[i] = idx[i] = sub[i] = 0 , adj[i].clear(); } bool is_anc(int u , int v) { if(idx[v] >= idx[u] && idx[v] <= idx[u] + sub[u] - 1) return true; return false; } int solve(int n , int m , vector < int > F , vector < vector < int > > S) { get_dep(n , m , F); vector < int > A; for(int i = 0;i < n - 1;i++) { A.push_back(S[0][i]); } int res = 1; for(int bit = 0;bit < (1 << (int)A.size());bit++) { vector < vector < int > > g; vector < int > cur; for(int i = 0;i < n - 1;i++) { cur.push_back(A[i]); if((1 << i) & bit){ if(cur.size() > 0) g.push_back(cur); cur.clear(); } } if(cur.size()) g.push_back(cur); int k = g.size(); vector < int > com(n + 1 , -1); bool can = 1; for(int i = 0;i < g.size();i++) { for(int x : g[i]) com[x] = i; } for(int i = 0;i < A.size() - 1;i++){ for(int j = i + 1;j < A.size();j++){ if(com[A[j]] > com[A[i]] && dep[A[j]] > dep[A[i]] && is_anc(A[i] , A[j]) == 1) { can = 0; } } } if(can){ res = max(res , k); } } fix(); return res; }
#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...