# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
832758 | TS_2392 | Sailing Race (CEOI12_race) | C++14 | 445 ms | 3456 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>
using namespace std;
#define fileIO(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define SPEED {ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);}
template<class T1, class T2> bool minimize(T1 &a, T2 b){return a > b ? a = b, true : false;}
template<class T1, class T2> bool maximize(T1 &a, T2 b){return a < b ? a = b, true : false;}
const int N = 505;
int n, type, res, res_vtx, nxt[N], prv[N];
int adj[N][N], dp[N][N][2], dp2[N][N][2];
int main(){
SPEED;
cin >> n >> type;
for(int u = 1, v; u <= n; ++u){
cin >> v;
while(v){
adj[u][v] = 1;
cin >> v;
}
nxt[u] = u + 1; prv[u] = u - 1;
}
nxt[n] = 1; prv[1] = n;
for(int len = 2; len <= n; ++len){
for(int i = 1; i <= n; ++i){
int j = i + len - 1;
if(j > n) j -= n;
//compute dp[i][j][0]
if(adj[i][j]) dp[i][j][0] = 1 + dp[j][nxt[i]][1];
for(int k = i; k != j; k = nxt[k]) if(adj[i][k]){
maximize(dp[i][j][0], max(dp[k][j][0], dp[k][nxt[i]][1]) + 1);
}
//compute dp[j][i][1]
if(adj[j][i]) dp[j][i][1] = 1 + dp[i][prv[j]][0];
for(int k = j; k != i; k = prv[k]) if(adj[j][k]){
maximize(dp[j][i][1], max(dp[k][prv[j]][0], dp[k][i][1]) + 1);
}
if(maximize(res, dp[i][j][0])) res_vtx = i;
if(maximize(res, dp[j][i][1])) res_vtx = j;
}
}
cout << res << '\n' << res_vtx;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |