Submission #1367966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1367966		KALARRY	9월 (APIO24_september)	C++17	59 / 100	96 ms	20712 KiB

september

//chockolateman

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

using namespace std;

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

void dfs(int v,int p)
{
    if(v != 0)
    {
        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-1 ; j++)
            pos[S[i][j]][i] = 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]][i]);
        if(cur_pos==lim)
            ans++;
        cur_pos++;
    }
    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: 9 / 9
• Subtask 5: 5 / 5
• Subtask 6: 0 / 11
• Subtask 7: 9 / 9
• Subtask 8: 11 / 11
• Subtask 9: 9 / 9
• Subtask 10: 0 / 16