# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
375201 | jhwest2 | 마상시합 토너먼트 (IOI12_tournament) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long lint;
typedef pair<int, int> pint;
typedef pair<lint, lint> plint;
const int MAX = 2e5 + 10;
int n, c, r, K[MAX], S[MAX], E[MAX], Par[MAX], Dp[MAX], Dep[MAX];
vector<int> G[MAX];
void update(int a) {
K[a] = 0;
for (int x : G[a]) K[a] = max(K[a], K[x]);
}
int GetPestPosition(int N, int C, int R, int *k, int *s, int *e) {
n = N; c = C; r = R; K[0] = r;
for (int i = 1; i < n; i++) K[i] = k[i - 1];
for (int i = 0; i < c; i++) S[i] = s[i], E[i] = e[i];
vector<int> V; int p = 0;
for (int i = 0; i < c; i++) {
while (V.size() <= E[i]) V.push_back(p++);
while (V.size() > S[i]) Par[V.back()] = n, V.pop_back();
V.push_back(n++);
}
for (int i = 0; i < n - 1; i++) {
G[Par[i]].push_back(i); K[Par[i]] = max(K[Par[i]], K[i]);
}
for (int i = n - 2; i >= 0; i--) {
if (K[Par[i]] == K[i]) Dp[i] = Dp[Par[i]] + 1;
Dep[i] = Dep[Par[i]] + 1;
}
for (int j = 0; j < n; j++) cout << Dp[j] << ' ';
cout << '\n';
pint ans = { -1, -1 }; vector<int> W;
for (int i = 0; i < n - c - 1; i++) {
ans = max(ans, { Dp[i], -i }); swap(K[i], K[i + 1]);
int x = i, y = i + 1;
if (Dep[x] < Dep[y]) swap(x, y);
W.push_back(x); W.push_back(y);
while (Dep[x] > Dep[y] && Par[x] != Par[y]) {
update(Par[x]), x = Par[x], W.push_back(x);
}
while (Par[x] != Par[y]) {
update(Par[x]); update(Par[y]);
x = Par[x]; y = Par[y];
W.push_back(x); W.push_back(y);
}
while (!W.empty()) {
int u = W.back(); W.pop_back();
if (K[Par[u]] == K[u]) Dp[u] = Dp[Par[u]] + 1;
else Dp[u] = 0;
}
}
ans = max(ans, { Dp[n - c - 1], 1 + c - n });
return -ans.vb
}