제출 #1344625

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1344625		PakinDioxide	9월 (APIO24_september)	C++17	100 / 100	84 ms	15892 KiB

september

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

using namespace std;

const int mxN = 1e5+5;

vector <int> adj[mxN];
int T[mxN], T2[mxN];

void dfs(int u, int p, int mn) {
    T[u] = min(T[u], mn);
    for (auto v : adj[u]) dfs(v, u, T[u]);
}

int solve(int N, int M, vector <int> F, vector <vector <int>> S) {
    for (int i = 0; i < N; i++) adj[i].clear();
    for (int i = 0; i < N; i++) if (F[i] > -1) adj[F[i]].emplace_back(i);
    for (int i = 0; i < N; i++) T2[i] = INT_MAX;
    for (auto &v : S) {
        T[0] = INT_MAX;
        for (int i = 0; i < N-1; i++) T[v[i]] = i;
        dfs(0, 0, INT_MAX);
        for (int i = 0; i < N; i++) T2[i] = min(T2[i], T[i]);
    }
    int ans = INT_MAX;
    for (auto &v : S) {
        int mn[N];
        mn[N-1] = INT_MAX;
        for (int i = N-2; i >= 0; i--) mn[i] = min(T2[v[i]], mn[i+1]);
        int cnt = 0;
        for (int i = 0; i < N-1; i++) if (mn[i+1] > i) cnt++;
        ans = min(ans, cnt);
    }
    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