#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
void solve(){
int n, k;
cin >> n >> k;
vector<vector<int>> adj(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);
mat[i][x] = true;
}
}
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, 0)), mg(n+1, vector<int>(n+1, 0));
//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;
}
}
}
if(k == 0){
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;
}
}
cout << ans << "\n" << ansi;
return;
}
}
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 |
Incorrect |
1 ms |
336 KB |
Unexpected end of file - int32 expected |
| 3 |
Incorrect |
1 ms |
336 KB |
Unexpected end of file - int32 expected |
| 4 |
Incorrect |
1 ms |
336 KB |
Unexpected end of file - int32 expected |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
508 KB |
Unexpected end of file - int32 expected |
| 7 |
Correct |
2 ms |
336 KB |
Output is correct |
| 8 |
Incorrect |
2 ms |
336 KB |
Unexpected end of file - int32 expected |
| 9 |
Correct |
4 ms |
592 KB |
Output is correct |
| 10 |
Correct |
5 ms |
592 KB |
Output is correct |
| 11 |
Correct |
6 ms |
592 KB |
Output is correct |
| 12 |
Incorrect |
31 ms |
1104 KB |
Unexpected end of file - int32 expected |
| 13 |
Incorrect |
87 ms |
1984 KB |
Unexpected end of file - int32 expected |
| 14 |
Correct |
195 ms |
2896 KB |
Output is correct |
| 15 |
Incorrect |
456 ms |
4432 KB |
Unexpected end of file - int32 expected |
| 16 |
Incorrect |
468 ms |
4688 KB |
Unexpected end of file - int32 expected |
| 17 |
Incorrect |
452 ms |
4432 KB |
Unexpected end of file - int32 expected |
| 18 |
Correct |
364 ms |
4680 KB |
Output is correct |
| 19 |
Incorrect |
508 ms |
4776 KB |
Unexpected end of file - int32 expected |
| 20 |
Incorrect |
504 ms |
4688 KB |
Unexpected end of file - int32 expected |
