#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) {
if (l == x) return 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) || tren == i) 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) || tren == i) 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
race.cpp: In function 'int main()':
race.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
45 | scanf("%d%d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~
race.cpp:49:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
49 | scanf("%d", &x);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2260 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4436 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4436 KB |
Output is correct |
| 4 |
Correct |
5 ms |
4556 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2260 KB |
Output is correct |
| 6 |
Correct |
7 ms |
4652 KB |
Output is correct |
| 7 |
Correct |
6 ms |
2416 KB |
Output is correct |
| 8 |
Correct |
10 ms |
4616 KB |
Output is correct |
| 9 |
Correct |
8 ms |
2388 KB |
Output is correct |
| 10 |
Correct |
22 ms |
2388 KB |
Output is correct |
| 11 |
Correct |
11 ms |
2428 KB |
Output is correct |
| 12 |
Correct |
147 ms |
5256 KB |
Output is correct |
| 13 |
Correct |
253 ms |
5692 KB |
Output is correct |
| 14 |
Correct |
82 ms |
2388 KB |
Output is correct |
| 15 |
Correct |
1503 ms |
6716 KB |
Output is correct |
| 16 |
Correct |
1876 ms |
6876 KB |
Output is correct |
| 17 |
Correct |
1480 ms |
6716 KB |
Output is correct |
| 18 |
Correct |
99 ms |
2516 KB |
Output is correct |
| 19 |
Correct |
2258 ms |
6960 KB |
Output is correct |
| 20 |
Correct |
2264 ms |
6964 KB |
Output is correct |
