Submission #55226

#TimeUsernameProblemLanguageResultExecution timeMemory
55226linkretSailing Race (CEOI12_race)C++14
100 / 100
1387 ms7212 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 505, inf = 1e9; int n, id; vector<int> adj[maxn]; vector<int> radj[maxn]; bool between(int l, int r, int i) { if(l > r) { return i >= l || i <= r; } else { return i >= l && i <= r; } } int dist(int i, int j) { if(i <= j) return j - i; return n - i + j; } int dp[2][2][maxn][maxn]; int f[2][maxn][maxn]; int main() { ios_base::sync_with_stdio(false); cin >> n >> id; for(int i = 0, j; i < n; i++) { while(true) { cin >> j; if(!j) break; j--; adj[i].push_back(j); radj[j].push_back(i); } } for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { f[0][i][j] = -1; f[1][i][j] = -1; for(int k : radj[i]) { if(between(j, i, k)) continue; if(f[0][i][j] == -1) f[0][i][j] = k; if(dist(i, f[0][i][j]) < dist(i, k)) f[0][i][j] = k; } for(int k : radj[i]) { if(between(i, j, k)) continue; if(f[1][i][j] == -1) f[1][i][j] = k; if(dist(i, f[1][i][j]) > dist(i, k)) f[1][i][j] = k; } } } for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { dp[1][0][i][j] = -inf; dp[1][1][i][j] = -inf; } } for(int i = 0; i < n; i++) { dp[1][0][i][i] = 0; dp[1][1][i][i] = 0; } for(int len = 1; len < n; len++) { for(int i = 0; i < n; i++) { int j = (i + len) % n; for(int k : radj[j]) { if(between(i, j, k)) { dp[1][0][i][j] = max(dp[1][0][i][j], 1 + dp[1][0][i][k]); } } for(int k : radj[i]) { if(between(i, j, k)) { dp[1][1][i][j] = max(dp[1][1][i][j], 1 + dp[1][1][k][j]); } } for(int k : adj[i]) { if(between(i, j, k)) { dp[0][0][i][j] = max(dp[0][0][i][j], 1 + max(dp[0][1][(i + 1) % n][k], dp[0][0][k][j])); } } for(int k : adj[j]) { if(between(i, j, k)) { dp[0][1][i][j] = max(dp[0][1][i][j], 1 + max(dp[0][1][i][k], dp[0][0][k][(j - 1 + n) % n])); } } } } int mxm = 0, t = 0; for(int i = 0; i < n; i++) { int tmp = dp[0][0][i][(i - 1 + n) % n]; if(tmp > mxm) { mxm = tmp; t = i; } } if(id) { for(int i = 0; i < n; i++) { for(int j = 0, l; j < n; j++) { if(i == j) continue; for(int k : adj[j]) { if(i == k || j == k) continue; if(between(j, k, i)) l = f[0][i][j]; else l = f[1][i][j]; if(l == i || l == j || l == k || l == -1) continue; if(between(j, k, i)) { int tmp = 0; if(between(k, j, l)) { tmp = dp[1][1][j][i] + 2 + max(dp[0][1][(i + 1) % n][k], dp[0][0][k][l]); } if(tmp > mxm) { mxm = tmp; t = l; } } else { int tmp = 0; if(between(j, k, l)) { tmp = dp[1][0][i][j] + 2 + max(dp[0][0][k][(i - 1 + n) % n], dp[0][1][l][k]); } if(tmp > mxm) { mxm = tmp; t = l; } } } } } } cout << mxm << endl << t + 1 << endl; // for(int i = 0; i < n; i++) { // for(int j = 0; j < n; j++) { // int k = dp[0][1][i][j]; // if(k < 0) // cout << 'x' << " "; // else // cout << k << " "; // } // cout << endl; // } // for(int i = 0; i < n; i++) { // for(int j = 0; j < n; j++) { // cout << f[i][j] << " "; // } // cout << endl; // } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...