#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
typedef long long ll;
typedef pair<int, int> point;
const int MAXN = 505, inf = 1e9;
bool inside(int l, int r, int k, int w) {
if(w == l || w == r || l == r) return false;
if(l > r) {
swap(r, l);
k ^= 1;
}
if(!k) {
return (w > l && r > w);
}
return !(w > l && r > w);
}
int n, K;
vector<int> e[MAXN];
int mem[MAXN][MAXN][2];
int calc(int l, int r, int k) {
if(mem[l][r][k] != -1) {
return mem[l][r][k];
}
int ret = 0;
for(auto w: e[l]) {
if(inside(l, r, k, w)) {
ret = max(ret, 1 + calc(w, r, k));
ret = max(ret, 1 + calc(w, l, k ^ 1));
}
}
return mem[l][r][k] = ret;
}
int mem2[MAXN][MAXN][2];
int ravno(int l, int r, int k) {
if(mem2[l][r][k] != -1) {
return mem2[l][r][k];
}
int ret = -inf;
for(auto w: e[l]) {
if(inside(l, r, k, w)) {
ret = max(ret, 1 + ravno(w, r, k));
}
if(w == r) {
ret = max(ret, 1);
}
}
return mem2[l][r][k] = ret;
}
int dist(int k, int j, int f) {
int len;
if(k > j) len = k - j;
else len = n - j + k;
if(f) len = n - len;
return len;
}
int nxt[MAXN][MAXN][2];
void init() {
memset(nxt, -1, sizeof nxt);
REP(k, n) for(auto i: e[k]) REP(j, n) REP(f, 2) {
if(inside(i, j, f, k)) continue;
if(nxt[i][j][f] == -1 || dist(nxt[i][j][f], j, f) > dist(k, j, f)) {
nxt[i][j][f] = k;
}
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
memset(mem, -1, sizeof mem);
memset(mem2, -1, sizeof mem2);
cin >> n >> K;
REP(i, n) {
int x; cin >> x;
while(x) {
e[i].push_back(x - 1);
cin >> x;
}
}
int sol = 0, ind = 1;
REP(i, n) for(auto j: e[i]) {
sol = max(sol, calc(j, i, 1));
sol = max(sol, calc(j, i, 0));
if(max(calc(j, i, 1), calc(j, i, 0)) == sol) {
ind = i + 1;
}
}
sol ++;
if(!K) {
cout << sol << endl << ind << endl;
return 0;
}
init();
REP(i, n) REP(j, n) for(auto l: e[j]) REP(f, 2) {
int k = nxt[i][j][f];
if(k == -1 || !inside(j, l, f, k) || !inside(i, j, 1 - f, l)) continue;
// cout << i _ j _ k _ l _ ravno(i, j, f) << endl;
int ns = 2 + max(calc(l, k, 1 - f), calc(l, i, f)) + ravno(i, j, f);
if(ns >= sol) {
ind = k + 1;
sol = ns;
}
}
cout << sol << endl << ind << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4348 KB |
Output is correct |
2 |
Correct |
7 ms |
6376 KB |
Output is correct |
3 |
Correct |
9 ms |
6512 KB |
Output is correct |
4 |
Correct |
9 ms |
6636 KB |
Output is correct |
5 |
Correct |
8 ms |
6636 KB |
Output is correct |
6 |
Correct |
11 ms |
6636 KB |
Output is correct |
7 |
Correct |
10 ms |
6636 KB |
Output is correct |
8 |
Correct |
14 ms |
6636 KB |
Output is correct |
9 |
Correct |
12 ms |
6636 KB |
Output is correct |
10 |
Correct |
27 ms |
6636 KB |
Output is correct |
11 |
Correct |
16 ms |
6636 KB |
Output is correct |
12 |
Correct |
111 ms |
6672 KB |
Output is correct |
13 |
Correct |
221 ms |
6764 KB |
Output is correct |
14 |
Correct |
119 ms |
6764 KB |
Output is correct |
15 |
Correct |
1315 ms |
6884 KB |
Output is correct |
16 |
Correct |
1567 ms |
7108 KB |
Output is correct |
17 |
Correct |
1428 ms |
7124 KB |
Output is correct |
18 |
Correct |
153 ms |
7124 KB |
Output is correct |
19 |
Correct |
1993 ms |
7368 KB |
Output is correct |
20 |
Correct |
2303 ms |
7524 KB |
Output is correct |