| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 681266 | vjudge1 | Sailing Race (CEOI12_race) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int N = 510;
int n, dp[N][N][2], rdp[N][N][2];
vector<int> g[N];
int inside(int l, int r, int x){
if(l == x || x == r) return -1;
if(l < r) return l < x && x < r;
return l < x || x < r;
}
int solve(int l, int r, bool f){
int v = !f * l + f * r;
if(dp[l][r][f] != -1) return dp[l][r][f];
dp[l][r][f] = 1;
for(int u : g[v]){
if(inside(l, r, u) == 1) dp[l][r][f] = max(dp[l][r][f], max(solve(l, u, 1), solve(u, r, 0)) + 1);
}
return dp[l][r][f];
}
int rec(int l, int r, bool f){
int v = !f * l + f * r;
if(rdp[l][r][f] != -1) return rdp[l][r][f];
rdp[l][r][f] = 1;
for(int u : g[v]){
int nl = v, nr = u;
if(f){
nl = u;
nr = v;
}
if(inside(l, r, u) == 1) rdp[l][r][f] = max(rdp[l][r][f], rec(nl, nr, f) + 1);
}
for(int u : g[v]){
if(inside(l, r, u) == 0) rdp[l][r][f] = max(rdp[l][r][f], rec())
}
return rdp[l][r][f];
}
int main(){
memset(dp, -1, sizeof(dp));
int k;
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++){
while(1){
int x;
scanf("%d", &x);
if(!x) break;
g[i].pb(x);
}
}
int ans = 1;
int ind = 1;
for(int v = 1; v <= n; v++){
for(int u : g[v])
if(ans < max(solve(v, u, 1), solve(u, v, 0)) + 1){
ans = max(solve(v, u, 1), solve(u, v, 0)) + 1;
ind = v;
}
}
/*printf("%d\n", ans);
if(k){
for(int v = 1; v <= n; v++)
for(int u : g[v])
if(ans < max(rec(v, u, 1), rec(u, v, 0)) + 1){
ans = max(rec(v, u, 1), rec(u, v, 0)) + 1;
ind = v;
}
}*/
printf("%d\n%d\n", ans, ind);
return 0;
}