Submission #1083010

#TimeUsernameProblemLanguageResultExecution timeMemory
1083010djs100201September (APIO24_september)C++17
0 / 100
1068 ms2652 KiB
#include <bits/stdc++.h> // #include "september.h" #define all(v) v.begin(), v.end() using namespace std; using ll = long long; using P = pair<ll, ll>; using PP = pair<ll, P>; const ll n_ = 1e5 + 10, inf = (ll)2e9 * (ll)1e9 + 7, mod = 998244353; ll n, m, tc = 1, a, b, c, d, sum, x, y, z, base, ans, k; ll par[n_], mx[n_], L[n_], R[n_]; vector<ll> v[n_]; void dfs(ll x) { for (auto nxt : v[x]) { dfs(nxt); R[x] = max(R[x], R[nxt]); } } int solve(int N, int M, vector<int> F, vector<vector<int>> S) { n = N - 1, m = M; vector<ll> T; for (int i = 0; i <= n; i++) L[i] = inf, R[i] = -inf; for (int j = 0; j < m; j++) for (int i = 0; i < n; i++) { ll val = S[j][i]; L[val] = min(L[val], (ll)i); R[val] = max(R[val], (ll)i); } for (int i = 1; i <= n; i++) v[F[i]].push_back(i); dfs(0); vector<P> v; for (int i = 1; i <= n; i++) v.push_back({L[i], R[i]}); sort(all(v)); ll lim = -inf, ret = 0; for (auto [a, b] : v) { if (lim < a) { ret++; lim = b; } else lim = max(lim, b); } return ret; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...