#include <bits/stdc++.h>
#define cif(i, n) for(int i = 0; i < n; i++)
#define pif(i, n) for(int i = n-1; i >= 0; i--)
#define scan(a, __n) for(int __ = 0; __ < __n; __++)cin >> a[__];
// #define print(a, __n) for(int ___ = 0; ___ < __n; ___++)cout << a[___] << ' '; cout << '\n';
// #define int ll
#define fastIO ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
// #define fr first
// #define sc second
#define all(v) v.begin(), v.end()
#define c0 (v<<1)
#define c1 (c0|1)
#define md ((l+r)/2)
typedef long long ll;
typedef double ld;
using namespace std;
const int mod = 1e9+7;
const int maxN = 500+7;
const string fileName = "";
// const int maxFac = 1e6+7;
// ll fac[maxFac], _fac[maxFac];
// ll po(ll b, ll p){
// b %= mod;
// p %= mod-1;
// ll r = 1;
// while(p){
// if(p&1)r = r*b%mod;
// p >>= 1;
// b = b*b%mod;
// }
// return r;
// }
// ll choose(ll k, ll n){
// return fac[n]*_fac[k]%mod*_fac[n-k]%mod;
// }
// ll factorial(ll n, ll k){
// ll ret = 1;
// for(ll i = n; i >= n-k+1; i--){
// ret = ret*i%mod;
// }
// return ret;
// }
int dp[maxN][maxN][2];
int pd[maxN][maxN][2];
int fdp[maxN][maxN][2];
vector<int> nx[maxN][maxN][2];
vector<int> g[maxN], rg[maxN];
int n, k;
bool is_between(int l, int r, int x, bool dir){
return dir ^ ((l <= r) ? (l <= x && x <= r) : (x <= r || l <= x));
}
int ans, ind;
void cal(int i, int j, int dir, bool debug = 0){
if(debug){
// cout << i << " " << j << ' ' << dir << " : ";
// for(auto u : rg[i])cout << u << ' ';
// cout << '\n';
}
fdp[i][j][dir] = i;
for(auto u : rg[i]){
if(u == i || u == j)continue;
if(is_between(i, j, u, dir)){
dp[i][j][dir] = max(dp[i][j][dir], 1 + max(dp[u][i][1-dir], dp[u][j][dir]));
if(1+dp[u][i][1-dir] == dp[i][j][dir]){
fdp[i][j][dir] = fdp[u][i][1-dir];
}
if(1+dp[u][j][dir] == dp[i][j][dir]){
fdp[i][j][dir] = fdp[u][j][dir];
}
}
}
pd[i][j][dir] = dp[i][j][dir];
int inc[n];
memset(inc, 0, sizeof inc);
for(auto u : rg[i]){
if(is_between(i+1, j-1, u, dir)){
if(pd[i][j][dir] < 1 + pd[u][j][dir]){
for(auto v : nx[u][j][dir]){
if(v != u){
inc[v] = 1;
}
}
}
if(pd[i][j][dir] < 1 + pd[u][i][1-dir]){
for(auto v : nx[u][i][1-dir]){
if(v != u && is_between(i+1, j-1, v, dir)){
inc[v] = 1;
}
}
}
}
}
if(dp[i][j][dir] == 0){
for(auto u : rg[i])inc[u] = 1;
}
inc[i] = inc[j] = 0;
for(int q = 0; q < n; q++){
if(inc[q]){
nx[i][j][dir].push_back(q);
}
}
if(nx[i][j][dir].size()){
pd[i][j][dir]++;
}
}
void upd(int i, int j, int dir){
int aa = ans;
ans = max(ans, 1 + dp[i][j][dir]);
if(k)ans = max(ans, 1 + pd[i][j][dir]);
if(aa != ans){
if(nx[i][j][dir].size()){
ind = nx[i][j][dir][0];
}
else ind = fdp[i][j][dir];
}
}
void slv(){
cin >> n >> k;
for(int i = 0; i < n; i++){
while(true){
int x;
cin >> x;
if(x == 0)break;
x--;
g[i].push_back(x);
rg[x].push_back(i);
}
}
for(int l = 0; l < n; l++){
for(int i = 0, j; i < n; i++){
j = (i+l)%n;
cal(i, j, 0);
j = (i-l+n)%n;
if(i == 1 && j == 0){
cal(i, j, 1, 1);
}
else{
cal(i, j, 1);
}
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
// cout << i << ' ' << j << " : ";
// cout << dp[i][j][0] << ' ' << pd[i][j][0] << ' ' << fdp[i][j][0] << " | " << dp[i][j][1] << ' ' << pd[i][j][1] << ' ' << fdp[i][j][1] << '\n';
}
}
for(int i = 0; i < n; i++){
for(auto j : g[i]){
upd(i, j, 0);
upd(i, j, 1);
}
}
cout << ans << '\n';
cout << ind+1 << '\n';
}
/*
7 1
5 0
5 0
7 0
3 0
4 0
4 3 0
2 1 0
*/
signed main(){
if(fileName.size() > 0){
freopen("team.in", "r", stdin);
freopen("team.out", "w", stdout);
}
fastIO;
// cout << fixed << setprecision (15);
// fac[0] = 1;
// for(int i = 1; i < maxFac; i++)fac[i] = fac[i-1]*i%mod;
// _fac[maxFac-1] = po(fac[maxFac-1], mod-2);
// for(int i = maxFac-2; i >= 0; i--)_fac[i] = _fac[i+1]*(i+1)%mod;
// w[0] = 1;
// for(int i = 1; i < maxN; i++)w[i] = w[i-1]*p%mod;
// _w[maxN-1] = po(w[maxN-1], mod-2);
// for(int i = maxN-2; i >= 0; i--)_w[i] = _w[i+1]*p%mod;
int t = 1;
// cin >> t;
while(t--){
// cout << slv() << '\n';
slv();
// string s;
// cin >> s;
// bool x = slv();
// cout << (x?"YES":"NO") << '\n';
}
}
/*
*/
Compilation message
race.cpp: In function 'int main()':
race.cpp:195:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
195 | freopen("team.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
race.cpp:196:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
196 | freopen("team.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
12560 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
12636 KB |
Output isn't correct |
| 3 |
Correct |
6 ms |
12892 KB |
Output is correct |
| 4 |
Correct |
5 ms |
12892 KB |
Output is correct |
| 5 |
Correct |
7 ms |
13144 KB |
Output is correct |
| 6 |
Correct |
7 ms |
13324 KB |
Output is correct |
| 7 |
Correct |
9 ms |
13660 KB |
Output is correct |
| 8 |
Correct |
10 ms |
13704 KB |
Output is correct |
| 9 |
Correct |
13 ms |
13916 KB |
Output is correct |
| 10 |
Correct |
30 ms |
18772 KB |
Output is correct |
| 11 |
Incorrect |
16 ms |
14428 KB |
Output isn't correct |
| 12 |
Incorrect |
57 ms |
17416 KB |
Output isn't correct |
| 13 |
Correct |
128 ms |
20820 KB |
Output is correct |
| 14 |
Correct |
230 ms |
22612 KB |
Output is correct |
| 15 |
Correct |
509 ms |
30224 KB |
Output is correct |
| 16 |
Correct |
560 ms |
31316 KB |
Output is correct |
| 17 |
Incorrect |
565 ms |
31468 KB |
Output isn't correct |
| 18 |
Incorrect |
412 ms |
31352 KB |
Output isn't correct |
| 19 |
Correct |
595 ms |
32592 KB |
Output is correct |
| 20 |
Correct |
670 ms |
30980 KB |
Output is correct |
