//in the name of god//
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _ ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define MP make_pair
const int maxn = 500 + 10;
const int LG = 30;
const int Inf = 1e9 + 10;
int n, k;
int dp[maxn][maxn][2], dp1[maxn][maxn][2];
vector <int> g[maxn];
bool c[maxn][maxn];
int ans[maxn];
int nxt(int x){
return (x == 1) ? n : x - 1;
}
int prv(int x){
return (x == n) ? 1 : x + 1;
}
int Sol(int l, int r, int x){
int &anss = dp[l][r][x];
if(anss != -1)
return anss;
anss = 0;
if(x){
for(int i = nxt(l) ; i != r ; i = nxt(i))
if(c[r][i])
anss = max(anss, 1 + Sol(l, i, 1)),
anss = max(anss, 1 + Sol(r, i, 0));
}
else{
for(int i = prv(l) ; i != r ; i = prv(i))
if(c[r][i])
anss = max(anss, 1 + Sol(l, i, 0)),
anss = max(anss, 1 + Sol(r, i, 1));
}
return anss;
}
int mx, bst;
int Solv(int l, int r, int x){
if(l == r)
return 0;
int &anss = dp[l][r][x];
if(anss != -1)
return anss;
anss = -1 * Inf;
if(x){
for (int i = nxt(l) ; 1 ; i = nxt(i)){
if (c[l][i])
anss = max(anss, 1 + Solv(i, r, 1));
if(i == r)
break;
}
}
else{
for (int i = nxt(l) ; 1 ; i = nxt(i)){
if (c[l][i])
anss = max(anss, 1 + Solv(i, r, 0));
if(i == r)
break;
}
}
return anss;
}
bool chk1(int z, int l, int r){
if(l <= r)
return !(l <= z && z <= r);
swap(l, r);
return (l < z && z < r);
}
bool chk2(int z, int l, int r){
if(l <= r)
return (l < z && z < r);
swap(l, r);
return !(l <= z && z <= r);
}
int main(){_
cin >> n >> k;
for(int i = 1 ; i <= n ; i ++){
while(true){
int x;
cin >> x;
if(x == 0)
break;
g[i].push_back(x);
c[i][x] = 1;
}
}
memset(dp, -1, sizeof(dp));
for(int l = 1; l <= n; l ++)
for(int r = 1; r <= n; r ++){
Sol(r, l, 0);
Sol(r, l, 1);
if (c[l][r]){
ans[l] = max(ans[l], max(Sol(l, r, 0), Sol(l, r, 1)) + 1);
if (ans[l] > mx)
mx = ans[l],
bst = l;
}
}
if(k == 0){
cout << mx << '\n' << bst << '\n';
return 0;
}
memset(dp1, -1, sizeof dp1);
for(int l = 1 ; l <= n ; l ++)
for(int r = 1 ; r <= n ; r ++)
Solv(l, r, 0),
Solv(l, r, 1);
for(int i = 1 ; i <= n ; i ++)
for(int j = 1 ; j <= n ; j ++)
if(c[i][j]){
for (int s = nxt(j); s != i; s = nxt(s))
for (auto x : g[s])
if(chk1(x, i, j)){
ans[i] = max(ans[i], 2 + dp1[j][s][1] +
max(dp[j][x][0], dp[i][x][1]));
if (ans[i] > mx)
mx = ans[i],
bst = i;
}
for (int x = prv(j) ; x != i ; x = prv(x))
for (auto s : g[x])
if (chk2(s, i, j)){
ans[i] = max(ans[i], 2 + dp1[j][x][0] +
max(dp[j][s][1], dp[i][s][0]));
if (ans[i] > mx){
mx = ans[i];
bst = i;
}
}
}
cout << mx << '\n' << bst << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2252 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4300 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
4312 KB |
Output isn't correct |
| 4 |
Incorrect |
3 ms |
4300 KB |
Output isn't correct |
| 5 |
Correct |
3 ms |
2296 KB |
Output is correct |
| 6 |
Incorrect |
7 ms |
4428 KB |
Output isn't correct |
| 7 |
Correct |
6 ms |
2380 KB |
Output is correct |
| 8 |
Incorrect |
8 ms |
4428 KB |
Output isn't correct |
| 9 |
Correct |
11 ms |
2444 KB |
Output is correct |
| 10 |
Correct |
20 ms |
2484 KB |
Output is correct |
| 11 |
Correct |
13 ms |
2456 KB |
Output is correct |
| 12 |
Incorrect |
156 ms |
4424 KB |
Output isn't correct |
| 13 |
Incorrect |
276 ms |
4576 KB |
Output isn't correct |
| 14 |
Correct |
183 ms |
2508 KB |
Output is correct |
| 15 |
Incorrect |
2603 ms |
4788 KB |
Output isn't correct |
| 16 |
Execution timed out |
3091 ms |
4780 KB |
Time limit exceeded |
| 17 |
Incorrect |
2495 ms |
4804 KB |
Output isn't correct |
| 18 |
Correct |
296 ms |
2636 KB |
Output is correct |
| 19 |
Execution timed out |
3090 ms |
4804 KB |
Time limit exceeded |
| 20 |
Execution timed out |
3096 ms |
4812 KB |
Time limit exceeded |
