제출 #593484

#제출 시각아이디문제언어결과실행 시간메모리
593484Mamedov마상시합 토너먼트 (IOI12_tournament)C++17
49 / 100
1093 ms4784 KiB
#pragma GCC optimize ("O3") #include <bits/stdc++.h> #define pii pair<int, int> #define piii pair<pii, int> #define vi vector<int> #define vvi vector<vi> #define vpii vector<pii> #define vvpii vector<vpii> #define f first #define s second #define oo 1000000001 #define eb emplace_back #define pb push_back #define mpr make_pair #define size(v) (int)v.size() #define ln '\n' #define ull unsigned long long #define ll long long #define all(v) v.begin(), v.end() using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // sub 1-2, 49 points simple int dfs(int node, int N, int R, vi &val, vvi &g) { int res = 0; for (int to : g[node]) { res += dfs(to, N, R, val, g); val[node] = max(val[node], val[to]); } if (node >= N && val[node] == R) ++res; return res; } int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) { vvi g(2 * N); int nextNode = N - 1; vector<int>root(N), alive(N, 1); for (int i = 0; i < N; ++i) { root[i] = i; } for (int i = 0; i < C; ++i) { int node = -1, cnt = 0; while (cnt <= S[i]) { ++node; if (alive[node]) { ++cnt; } } g[++nextNode].eb(root[node]); root[node] = nextNode; while (cnt <= E[i]) { ++node; if (alive[node]) { g[nextNode].eb(root[node]); alive[node] = 0; ++cnt; } } } int best = 0, bestPos = 0; for (int i = 0; i < N; ++i) { vector<int>val(nextNode + 1, -1); for (int j = 0; j < i; ++j) { val[j] = K[j]; } val[i] = R; for (int j = i; j < N - 1; ++j) { val[j + 1] = K[j]; } int cur = dfs(nextNode, N, R, val, g); if (cur > best) { best = cur; bestPos = i; } } return bestPos; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...