Submission #1367938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1367938		KALARRY	September (APIO24_september)	C++17	16 / 100	67 ms	17584 KiB

september

//chockolateman

#include<bits/stdc++.h>
#include "september.h"

using namespace std;

int n,m,par[100005],pos[100005][5],need[100005][5];
vector<int> adj[100005];

void dfs(int v,int p)
{
    for(int i = 0 ; i < m ; i++)
        need[v][i] = pos[v][i];
    for(auto u : adj[v])
        if(u != p)
        {
            dfs(u,v);
            for(int i = 0 ; i < m ; i++)
                need[v][i] = max(need[v][i],need[u][i]);
        }
}

int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
	n = N;
    m = M;
    for(int i = 1 ; i <= N-1 ; i++)
    {
        adj[i].push_back(F[i]);
        adj[F[i]].push_back(i);
    }
    for(int i = 0 ; i < M ; i++)
        for(int j = 0 ; j < N ; j++)
            pos[S[i][j]][i] = j;
    dfs(0,0);
    int cur_pos[5] = {0,0,0,0,0};
    int lim[5] = {0,0,0,0,0};
    int ans = 0;
    while(cur_pos[0] < N-1)
    {

        for(int i = 0 ; i < M ; i++)
            lim[i] = max(lim[i],need[S[i][cur_pos[i]]][i]);
        bool good = true;
        for(int i = 0 ; i < M ; i++)
            if(cur_pos[i] < lim[i])
                good = false;
        if(good)
            ans++;
        for(int i = 0 ; i < M ; i++)
            cur_pos[i]++;
    }
    for(int i = 0 ; i < N ; i++)
        adj[i].clear();
    return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 14
• Subtask 3: 5 / 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