#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 = 1e6+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;
// }
vector<int> g[maxN], rg[maxN];
int n, k;
bool is_between(int l, int r, int x){
return (l <= r) ? (l <= x && x <= r) : (x <= r || l <= x);
}
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);
}
}
int ans = 0;
int dp[n+3][n+3][2];
int pd[n+3][n+3][2];
vector<int> nx[n+3][n+3][2];
memset(dp, 0, sizeof dp);
memset(pd, 0, sizeof pd);
int ind = 0;
for(int l = 0; l < n; l++){
for(int i = 0; i < n; i++){
int j = (i+l)%n;
if(i == j)continue;
for(auto u : g[i]){
if(u == i || u == j)continue;
if(is_between(i, j, u)){
dp[i][j][0] = max(dp[i][j][0], 1 + max(dp[u][i][1], dp[u][j][0]));
}
}
pd[i][j][0] = dp[i][j][0];
int inc[n];
memset(inc, 0, sizeof inc);
for(auto u : g[i]){
if(u == i || u == j)continue;
if(is_between(i, j, u)){
if(pd[i][j][0] < 1 + pd[u][j][0]){
for(auto u : nx[u][j][0])inc[u] = 1;
}
}
}
if(dp[i][j][0] == 0){
for(auto u : rg[i])inc[u] = 1;
}
inc[i] = inc[j] = 0;
for(int q = 0; q < n; q++){
if(inc[i]){
nx[i][j][0].push_back(q);
}
}
if(nx[i][j][0].size()){
pd[i][j][0]++;
}
int aa = ans;
ans = max(ans, 1 + dp[i][j][0]);
if(k)ans = max(ans, 1 + pd[i][j][0]);
if(aa != ans){
if(nx[i][j][0].size()){
ind = nx[i][j][0][0];
}
else ind = i;
}
}
for(int i = 0; i < n; i++){
int j = (i-l+n)%n;
if(i == j)continue;
for(auto u : g[i]){
if(u == i || u == j)continue;
if(!is_between(i, j, u)){
dp[i][j][1] = max(dp[i][j][1], 1 + max(dp[u][i][0], dp[u][j][1]));
}
}
pd[i][j][1] = dp[i][j][1];
int inc[n];
memset(inc, 0, sizeof inc);
for(auto u : g[i]){
if(u == i || u == j)continue;
if(!is_between(i, j, u)){
if(pd[i][j][1] < 1 + pd[u][j][1]){
for(auto u : nx[u][j][1])inc[u] = 1;
}
}
}
if(dp[i][j][1] == 0){
for(auto u : g[i])inc[u] = 1;
}
inc[i] = inc[j] = 0;
for(int q = 0; q < n; q++){
if(inc[i]){
nx[i][j][1].push_back(q);
}
}
if(nx[i][j][1].size()){
pd[i][j][1]++;
}
int aa = ans;
ans = max(ans, 1 + dp[i][j][1]);
if(k)ans = max(ans, 1 + pd[i][j][1]);
if(aa != ans){
if(nx[i][j][1].size()){
ind = nx[i][j][1][0];
}
else ind = i;
}
}
}
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:187:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
187 | freopen("team.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
race.cpp:188:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
188 | freopen("team.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
47228 KB |
Memory limit exceeded |
| 2 |
Runtime error |
22 ms |
47376 KB |
Memory limit exceeded |
| 3 |
Runtime error |
25 ms |
47280 KB |
Memory limit exceeded |
| 4 |
Runtime error |
23 ms |
47468 KB |
Memory limit exceeded |
| 5 |
Runtime error |
26 ms |
47476 KB |
Memory limit exceeded |
| 6 |
Runtime error |
24 ms |
47680 KB |
Memory limit exceeded |
| 7 |
Runtime error |
24 ms |
47656 KB |
Memory limit exceeded |
| 8 |
Runtime error |
25 ms |
47692 KB |
Memory limit exceeded |
| 9 |
Runtime error |
26 ms |
47820 KB |
Memory limit exceeded |
| 10 |
Runtime error |
28 ms |
48200 KB |
Memory limit exceeded |
| 11 |
Runtime error |
27 ms |
48060 KB |
Memory limit exceeded |
| 12 |
Runtime error |
40 ms |
50012 KB |
Memory limit exceeded |
| 13 |
Runtime error |
51 ms |
53268 KB |
Memory limit exceeded |
| 14 |
Runtime error |
79 ms |
57772 KB |
Memory limit exceeded |
| 15 |
Runtime error |
211 ms |
63680 KB |
Memory limit exceeded |
| 16 |
Runtime error |
249 ms |
63952 KB |
Memory limit exceeded |
| 17 |
Runtime error |
231 ms |
63564 KB |
Memory limit exceeded |
| 18 |
Runtime error |
128 ms |
63256 KB |
Memory limit exceeded |
| 19 |
Runtime error |
279 ms |
63936 KB |
Memory limit exceeded |
| 20 |
Runtime error |
279 ms |
63808 KB |
Memory limit exceeded |
