Submission #1367969

#	Time	Username	Problem	Language	Result	Execution time	Memory
1367969		KALARRY	September (APIO24_september)	C++17	100 / 100	89 ms	19092 KiB

september

//chockolateman

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

using namespace std;

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

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

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-1 ; j++)
            pos[S[i][j]] = max(pos[S[i][j]],j);
    dfs(0,0);
    int cur_pos = 0;
    int lim = 0;
    int ans = 0;
    while(cur_pos < N-1)
    {

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

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