제출 #1194402

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194402		ElayV13	9월 (APIO24_september)	C++20	0 / 100	7 ms	580 KiB

september

#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;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 5
• Subtask 4: 0 / 9
• Subtask 5: 0 / 5
• Subtask 6: 0 / 11
• Subtask 7: 0 / 9
• Subtask 8: 0 / 11
• Subtask 9: 0 / 9
• Subtask 10: 0 / 16