# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
680468 | kingfran1907 | Sailing Race (CEOI12_race) | C++17 | 539 ms | 2932 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long llint;
const int maxn = 510;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 20;
const int off = 1 << logo;
const int treesiz = off << 1;
int n, k;
vector< int > graph[maxn], graph2[maxn];
int dp[maxn][maxn][2];
int dist[2][maxn][maxn];
int bes[maxn][maxn][2];
int dis(int x, int y, bool flag = false) {
if (flag) swap(x, y);
return (y - x + n) % n;
}
bool check(int l, int r, int x, bool flag = false) {
return dis(l, x, flag) < dis(l, r, flag);
}
int f(int l, int r, bool flag) {
int &ret = dp[l][r][flag];
if (ret != -1) return ret;
ret = 0;
for (int tren : graph[l]) {
if (check(l, r, tren, flag))
ret = max(ret, 1 + max(f(tren, l, !flag), f(tren, r, flag)));
}
return ret;
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++) {
while (true) {
int x;
scanf("%d", &x);
if (x == 0) break;
graph[i].push_back(x - 1);
graph2[x - 1].push_back(i);
}
}
pair<int, int> sol = {-1, -1};
memset(dp, -1, sizeof dp);
for (int i = 0; i < n; i++) {
for (int tren : graph[i]) {
for (int k = 0; k < 2; k++) {
sol = max(sol, {1 + f(tren, i, k), i});
}
}
}
if (k == 0) {
printf("%d\n%d\n", sol.X, sol.Y + 1);
return 0;
}
/*for (int i = 0; i < n; i++) {
for (int j = (i + 1) % n; j != i; j++, j %= n) {
dist[0][i][j] = -inf;
for (int tren : graph2[j]) {
if (check(i, j, tren)) dist[0][i][j] = max(dist[0][i][j], 1 + dist[0][i][tren]);
}
}
for (int j = (i + n - 1) % n; j != i; j += n - 1, j %= n) {
dist[1][i][j] = -inf;
for (int tren : graph2[j]) {
if (check(i, j, tren, 1)) dist[1][i][j] = max(dist[1][i][j], 1 + dist[1][i][tren]);
}
}
}
memset(bes, -1, sizeof bes);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int tren : graph2[i]) {
for (int k = 0; k < 2; k++) {
if (check(i, j, tren, k)) continue;
if (bes[i][j][k] == -1) bes[i][j][k] = tren;
else if (dis(i, tren, k) < dis(i, bes[i][j][k], k)) bes[i][j][k] = tren;
}
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < 2; k++) {
if (i == j) continue;
for (int tren : graph[j]) {
int tr = bes[i][j][k];
if (tr == -1) continue;
if (!check(j, tren, tr, k) || !check(i, j, tren, 1 - k)) continue;
int ac = dist[k][i][j] + 2 + max(f(tren, tr, 1 - k), f(tren, i, k));
//printf("%d -> %d -> %d -> %d --- %d (%d)\n", tr, i, j, tren, ac, k);
//printf("%d + (%d %d)\n", dist[k][i][j], f(tren, tr, 1 - k), f(tren, i, k));
sol = max(sol, {ac, tr});
}
}
}
}
*/
printf("%d\n%d\n", sol.X, sol.Y + 1);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |