Submission #1197306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197306		batman3747	September (APIO24_september)	C++20	100 / 100	177 ms	16320 KiB

september

#include "bits/stdc++.h"
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << (#x) << " " << (x) << endl
#define SZ(s) ((int)s.size())
#define pb push_back
#define ff first
#define ss second
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

int solve(int n, int m, vi F, vector<vi> S){
    vi l(n, n), r(n);
    vector<vi> g(n);
    for(int i = 1; i < n; i ++) g[F[i]].pb(i);
    for(int j = 0; j < m; j ++){
        for(int i = 0; i < n - 1; i ++){
            int d = S[j][i];
            l[d] = min(l[d], i + 1);
            r[d] = max(r[d], i + 1);
        }
    }

    auto dfs = [&](auto &&dfs, int v, int p = -1) -> void {
        if(p != -1) l[v] = min(l[v], l[p]);
        for(int u : g[v]){
            dfs(dfs, u, v);
            r[v] = max(r[v], r[u]);
        }
    };

    dfs(dfs, 0);
    vector<pii> ln;
    for(int i = 1; i < n; i ++) ln.pb({l[i], r[i]});
    sort(all(ln));
    int ans = 0, cur = 0;
    for(auto [x, y] : ln){
        if(x > cur) ans ++;
        cur = max(cur, y);
    }
    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