#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()
typedef pair<int, pi> pii;
#define ld long double
const int maxn = 510;
const int INF = LLONG_MAX/2;
const int mod = 1e9+7;
int dp[maxn][maxn][2];
int dist[maxn][maxn][2]; //Best answer to go from i to j, clockwise or anticlockwise
vector <int> adjlist[maxn];
vector <int> backlist[maxn];
int n, K;
int dpf(int x, int jumps, int dir) {
if (dp[x][jumps][dir] != -1) return dp[x][jumps][dir];
int res = 0, need = 0;
for (auto i: adjlist[x]) {
if (dir == 1) {
if (i > x) need = i - x;
else need = n - x + i;
} else {
if (i < x) need = x - i;
else need = x + n - i;
}
if (need > jumps) continue;
res = max(res, dpf(i, jumps - need, dir) + 1);
res = max(res, dpf(i, need - 1, !dir) + 1);
}
return dp[x][jumps][dir] = res;
}
int SSS;
bool cmp(int a, int b) {
return (a - SSS + n) % n < (b - SSS + n) % n;
}
bool cmp2(int a, int b) {
return (a - SSS + n) % n > (b - SSS + n) % n;
}
int32_t main() {
FAST
// #ifndef ONLINE_JUDGE
// ifstream cin("input.txt");
// #endif
cin >> n >> K;
for (int i =0;i<n;i++) {
while (true) {
int x; cin >> x;
if (x == 0) break;
x--;
backlist[x].push_back(i);
adjlist[i].push_back(x);
}
}
pi rans = pi(0,0);
memset(dp,-1,sizeof dp);
for (int i =0;i<n;i++) {
rans = max(rans, pi(dpf(i, n-1, 1), i)); //1 is anticlockwise
}
if (K == 0) {
cout << rans.f << "\n" << rans.s;
return 0;
}
//Solve for K = 1
//Find best distance between a fixed start and X node
for (int s = 0; s < n; s++) {
int x = s;
for (auto i: adjlist[x]) {
dist[s][i][1] = 1;
}
x = (x + 1) % n;
while (x != s) {
int d = dist[s][x][1];
if (d == 0) goto skip1;
for (auto i: adjlist[x]) {
if ((i - s + n) % n > (x - s + n) % n) dist[s][i][1] = max(dist[s][i][1], d + 1);
}
skip1:;
x = (x + 1) % n;
}
x = s;
for (auto i: adjlist[x]) dist[s][i][0] = 1;
x = (x - 1 + n) % n;
while (x != s) {
int d = dist[s][x][0];
if (d == 0) goto skip2;
for (auto i: adjlist[x]) {
if ((i - s + n) % n < (x - s + n) % n)
dist[s][i][0] = max(dist[s][i][0], d + 1);
}
skip2:;
x = (x - 1 + n) % n;
}
}
for (int s = 0; s < n; s++) {
SSS = s;
sort(all(backlist[s]), cmp);
if (backlist[s].empty()) continue;
int pp = 0;
for (int x = (s + 1) % n; x != s; x = (x + 1) % n) {
if ((backlist[s][pp]-s+n)%n <= (x - s + n)%n) {
pp++;
}
if (pp >= backlist[s].size()) break;
if (dist[s][x][1] == 0) continue;
int TT = backlist[s][pp];
for (auto j : adjlist[x]) {
if ((j - s + n) % n <= (TT - s + n) % n) continue;
int jumps = n - ((j-s+n)%n) - 1;
int jumps2 = (j - s + n) % n - (TT-s+n)%n - 1;
int res = max(dpf(j, jumps, 1), dpf(j, jumps2, 0));
// cout << 1 << " s:" << s << " x:" << x << " T:" << TT << " j:" << j << " " << dist[s][x][1] + res + 2 << "\n";
rans = max(rans, pi(dist[s][x][1] + res + 2,TT));
}
}
sort(all(backlist[s]), cmp2);
pp = 0;
for (int x = (s - 1 + n) % n; x != s; x = (x - 1 + n) % n) {
if ((backlist[s][pp]-s+n)%n >= (x - s + n)%n) {
pp++;
}
if (pp >= backlist[s].size()) break;
if (dist[s][x][0] == 0) continue;
int TT = backlist[s][pp];
for (auto j : adjlist[x]) {
if (j == s or (j - s + n) % n >= (TT - s + n) % n) continue;
int jumps = (j-s+n)%n - 1;
int jumps2 = (TT-s+n)%n - (j-s+n)%n - 1;
int res = max(dpf(j,jumps,0), dpf(j,jumps2,1));
// cout << 0 << " s:" << s << " x:" << x << " T:" << TT << " j:" << j << " " << dist[s][x][0] + res + 2 << "\n";
rans = max(rans, pi(dist[s][x][0] + res + 2,TT));
}
}
}
cout << rans.f << "\n" << rans.s + 1;
}
Compilation message
race.cpp: In function 'int32_t main()':
race.cpp:129:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | if (pp >= backlist[s].size()) break;
| ~~~^~~~~~~~~~~~~~~~~~~~~
race.cpp:151:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
151 | if (pp >= backlist[s].size()) break;
| ~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4308 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4428 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4436 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4556 KB |
Output is correct |
| 5 |
Incorrect |
7 ms |
4428 KB |
Output isn't correct |
| 6 |
Correct |
5 ms |
4696 KB |
Output is correct |
| 7 |
Correct |
4 ms |
4428 KB |
Output is correct |
| 8 |
Correct |
5 ms |
4812 KB |
Output is correct |
| 9 |
Incorrect |
5 ms |
4448 KB |
Output isn't correct |
| 10 |
Correct |
9 ms |
4680 KB |
Output is correct |
| 11 |
Incorrect |
5 ms |
4556 KB |
Output isn't correct |
| 12 |
Correct |
52 ms |
6016 KB |
Output is correct |
| 13 |
Correct |
91 ms |
7060 KB |
Output is correct |
| 14 |
Incorrect |
49 ms |
4684 KB |
Output isn't correct |
| 15 |
Correct |
549 ms |
9260 KB |
Output is correct |
| 16 |
Correct |
714 ms |
9620 KB |
Output is correct |
| 17 |
Correct |
543 ms |
9248 KB |
Output is correct |
| 18 |
Incorrect |
49 ms |
4704 KB |
Output isn't correct |
| 19 |
Correct |
895 ms |
9820 KB |
Output is correct |
| 20 |
Correct |
901 ms |
9816 KB |
Output is correct |
