#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 1e9+9;
void solve(){
int n, k;
cin >> n >> k;
vector<vector<int>> adj(n+1), adj_rev(n+1);
vector<vector<bool>> mat(n+1, vector<bool>(n+1, false));
for(int i = 1; i <= n; i++){
while(true){
int x;
cin >> x;
if(x == 0) break;
adj[i].push_back(x);
adj_rev[x].push_back(i);
mat[i][x] = true;
}
}
vector<int> prv(n+1), nxt(n+1);
for(int i = 1; i <= n; i++){
prv[i] = i-1;
if(prv[i] == 0) prv[i] = n;
nxt[i] = i+1;
if(nxt[i] == n+1) nxt[i] = 1;
}
vector<vector<int>> f(n+1, vector<int>(n+1, 0)), g(n+1, vector<int>(n+1, 0)), mf(n+1, vector<int>(n+1, -INF)), mg(n+1, vector<int>(n+1, -INF));
//f is counter clockwise, g is clockwise such that path in region [i, j] start point is i, end point arbitrary
//mf is counter clockwise, mg is clockwise such that path in region [i, j], start point is i, end point is j
for(int i = 1; i <= n; i++){
for(int j : adj[i]){
f[i][j] = 1;
g[i][j] = 1;
mf[i][j] = 1;
mg[i][j] = 1;
}
}
auto chmax = [&](int &a, int b) -> void{
a = max(a, b);
};
for(int len = 2; len < n; len++){
for(int i = 1; i <= n; i++){
int j = i+len;
if(j > n) j-=n;
int k;
int nxt_i = i+1, prv_i = i-1;
if(nxt_i > n) nxt_i-=n;
if(prv_i == 0) prv_i+=n;
for(k = i; ; k++){
if(k == n+1){
k = 1;
}else if(k == 0){
k = n;
}
if(mat[i][k] == 1) chmax(f[i][j], mat[i][k]+max(f[k][j], g[k][nxt_i]));
chmax(mf[i][j], mf[i][k] + mf[k][j]);
if(k == j) break;
}
j = i-len;
if(j < 1) j+=n;
for(k = i; ; k--){
if(k == n+1){
k = 1;
}else if(k == 0){
k = n;
}
if(mat[i][k] == 1) chmax(g[i][j], mat[i][k]+max(g[k][j], f[k][prv_i]));
chmax(mg[i][j], mg[i][k] + mg[k][j]);
if(k == j) break;
}
}
}
int ans = -1, ansi = -1;
for(int i = 1; i <= n; i++){
int j = i-1;
if(j == 0) j+=n;
if(ans < f[i][j]){
ans = f[i][j];
ansi = i;
}
j = i+1;
if(j == n+1) j-=n;
if(ans < g[i][j]){
ans = g[i][j];
ansi = i;
}
}
if(k == 0){
cout << ans << "\n" << ansi;
return;
}
auto dist = [&](int i, int j) -> int{
if(j < i) j+=n;
return j-i;
};
auto distc = [&](int i, int j) -> int{
if(i < j) i+=n;
return i-j;
};
for(int B = 1; B <= n; B++){
for(int C = 1; C <= n; C++){
if(B == C) continue;
int A = -1, mn = 1e9;
for(int it : adj_rev[B]){
if(dist(C, it) < mn && it != C && it != B){
mn = dist(C, it);
A = it;
}
}
if(A == -1 || dist(B, A)+dist(A,C) == dist(B, C)) continue;
for(int D : adj[C]){
if(dist(A, D)+dist(D, B) != dist(A, B) || D == A || D == B || D == C) continue;
int cost = 1 + mf[B][C] + 1 + max(g[D][nxt[A]], f[D][prv[B]]);
if(ans < cost){
ans = cost;
ansi = A;
}
}
}
}
for(int B = 1; B <= n; B++){
for(int C = 1; C <= n; C++){
if(B == C) continue;
int A = -1, mn = 1e9;
for(int it : adj_rev[B]){
if(distc(C, it) < mn && it != C && it != B){
mn = distc(C, it);
A = it;
}
}
if(A == -1 || distc(B, A)+distc(A, C) == distc(B, C)) continue;
for(int D : adj[C]){
if(distc(A, D)+distc(D, B) != distc(A, B) || D == A || D == B || D == C) continue;
int cost = 1 + mg[B][C] + 1 + max(f[D][prv[A]], g[D][nxt[B]]);
if(ans < cost){
ans = cost;
ansi = A;
}
}
}
}
cout << ans << "\n" << ansi;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//freopen("main.inp", "r", stdin);
//freopen("main.out", "w", stdout);
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
2 ms |
336 KB |
Output is correct |
| 6 |
Correct |
2 ms |
336 KB |
Output is correct |
| 7 |
Correct |
2 ms |
608 KB |
Output is correct |
| 8 |
Correct |
3 ms |
592 KB |
Output is correct |
| 9 |
Correct |
4 ms |
592 KB |
Output is correct |
| 10 |
Correct |
5 ms |
760 KB |
Output is correct |
| 11 |
Correct |
6 ms |
592 KB |
Output is correct |
| 12 |
Correct |
49 ms |
1228 KB |
Output is correct |
| 13 |
Correct |
109 ms |
1872 KB |
Output is correct |
| 14 |
Correct |
196 ms |
3400 KB |
Output is correct |
| 15 |
Correct |
585 ms |
4688 KB |
Output is correct |
| 16 |
Correct |
641 ms |
4944 KB |
Output is correct |
| 17 |
Correct |
627 ms |
4864 KB |
Output is correct |
| 18 |
Correct |
379 ms |
4688 KB |
Output is correct |
| 19 |
Correct |
736 ms |
4944 KB |
Output is correct |
| 20 |
Correct |
704 ms |
5108 KB |
Output is correct |
