# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
55265 | paulica | Sailing Race (CEOI12_race) | C++14 | 3056 ms | 4984 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>
using namespace std;
#define _ << " _ " <<
#define TRACE(x) cout << #x << " = " << x << endl
const int MaxN = 510;
int n, m;
int sol, start;
bool con[MaxN][MaxN];
int dpA[MaxN][MaxN][2], dpB[MaxN][MaxN][2];
int nxt(int i, int d) {
if (d == 1) return i == n - 1 ? 0 : i + 1;
else return i == 0 ? n - 1 : i - 1;
}
void check(int cnt, int s) {
if (cnt > sol) {
sol = cnt;
start = s;
}
}
void solveS(int x, int s, int d) {
int maxB = 0, t = -1;
for (int i = nxt(s, d); i != x; i = nxt(i, d)) {
if (con[s][i]) {
t = i;
check(dpA[t][x][d] + maxB, s);
}
if (con[x][i])
maxB = max(maxB, dpB[i][s][1 - d]);
}
}
void solveT(int x, int t, int d) {
int maxB = 0, s = -1;
for (int i = nxt(x, d); i != t; i = nxt(i, d))
if (con[i][t]) {
s = i;
break;
}
if (s == -1) return;
for (int i = nxt(s, d); i != t; i = nxt(i, d))
if (con[x][i])
maxB = max(maxB, dpB[i][t][d]);
check(dpA[t][x][d] + maxB, s);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++) {
int j;
for (cin >> j; j != 0; cin >> j)
con[i][j - 1] = true;
}
for (int d : {0, 1})
for (int i = 0; i < n; i++) {
dpA[i][i][d] = 1;
for (int j = nxt(i, d); j != i; j = nxt(j, d)) {
int& dp = dpA[i][j][d];
if (con[i][j]) dp = 2;
else dp = 0;
for (int k = nxt(i, d); k != j; k = nxt(k, d))
if (con[k][j] && dpA[i][k][d] > 0) dp = max(dp, dpA[i][k][d] + 1);
}
}
for (int len = 1; len < n; len++)
for (int d : {0, 1})
for (int i = 0; i < n; i++) {
int j;
if (d == 1) j = i + len >= n ? i + len - n : i + len;
else j = i - len < 0 ? i - len + n : i - len;
int& dp = dpB[i][j][d];
dp = 1;
for (int k = nxt(i, d); k != j; k = nxt(k, d))
if (con[i][k]) {
dp = max(dp, dpB[k][j][d] + 1);
dp = max(dp, dpB[k][i][1 - d] + 1);
}
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int d : {0, 1})
if (con[i][j]) check(dpB[j][i][d], i);
if (m == 1)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (i != j) {
solveS(i, j, 0);
solveS(i, j, 1);
solveT(i, j, 0);
solveT(i, j, 1);
}
cout << sol << "\n" << start + 1 << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |