제출 #1202426

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1202426		Nelt	September (APIO24_september)	C++20	100 / 100	157 ms	19056 KiB

september

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

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll N = 1e5 + 5;
vector<ll> g[N];
ll need[N];
void dfs(ll v)
{
    for (ll to : g[v])
        dfs(to), need[v] = max(need[v], need[to]);
}
int solve(int n, int m, std::vector<int> p, std::vector<std::vector<int>> a)
{
    ll deg[n + 1];
    p.insert(p.begin(), 0);
    for (ll i = 1; i <= n; i++)
        g[i].clear();
    for (ll i = 1; i <= n; i++)
        p[i]++, g[p[i]].push_back(i);
    for (ll i = 1; i <= n; i++)
        deg[i] = 0;
    for (ll i = 1; i <= n; i++)
        deg[p[i]]++;
    ll freq[n + 1], cnt = 0;
    for (ll i = 1; i <= n; i++)
        freq[i] = 0;
    for (ll i = 0; i < m; i++)
    {
        a[i].insert(a[i].begin(), 0);
        for (ll j = 1; j < n; j++)
            a[i][j]++;
    }
    for (ll i = 1; i < n; i++)  need[a[0][i]] = i;
    dfs(1);
    ll ans = 0, mx = 0;
    for (ll i = 1; i < n; i++)
    {
        for (ll j = 0; j < m; j++)
        {
            cnt += !freq[a[j][i]];
            freq[a[j][i]]++;
            cnt -= freq[a[j][i]] == m;
        }
        mx = max(mx, need[a[0][i]]);
        if (!cnt and mx <= i)
            ans++;
    }
    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