제출 #1194402

#제출 시각아이디문제언어결과실행 시간메모리
1194402ElayV13September (APIO24_september)C++20
0 / 100
7 ms580 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]; void dfs(int v , int p) { for(int u : adj[v]){ if(u == p) continue; dep[u] = dep[v] + 1; dfs(u , v); } } 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() { for(int i = 0;i < N;i++) dep[i] = 0 , adj[i].clear(); } int solve(int n , int m , vector < int > F , vector < vector < int > > S) { get_dep(n , m , F); int res = -1; for(int bit = 0;bit < (1 << (n - 1));bit++) { vector < vector < vector < int > > > groups(m); bool cut[n]; fill(cut , cut + n , false); for(int i = 0;i < n - 1;i++) { if((1 << i) & bit) cut[i] = 1; } vector < int > cur; for(int turn = 0;turn < m;turn++) { vector < int > cur; for(int i = 0;i < n - 1;i++) { cur.push_back(S[turn][i]); if(cut[i]){ groups[turn].push_back(cur); cur.clear(); } } if(cur.size()) groups[turn].push_back(cur); } int k = -1; for(vector < vector < int > > v : groups) k = max(k , (int)v.size()); bool can = 1; for(vector < vector < int > > v : groups) { for(int i = 0;i < v.size() - 1;i++) { int M1 = INF; for(int x : v[i]) M1 = min(M1 , dep[x]); for(int j = i + 1;j < v.size();j++) { int M2 = -INF; for(int x : v[j]) M2 = max(M2 , dep[x]); if(M2 > M1) 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...