Submission #55219

#TimeUsernameProblemLanguageResultExecution timeMemory
55219dfistricSailing Race (CEOI12_race)C++14
40 / 100
481 ms2940 KiB
#include <bits/stdc++.h> #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define REP(i, n) FOR(i, 0, n) using namespace std; const int MAXN = 510; vector <int> ve[MAXN]; int num_ways[MAXN][MAXN][2]; bool inside(int x, int y, int z, int t) { if (t == 0) swap(x, y); if (x < y) { return ((z > x) && (z < y)); } return ((z > x) || (z < y)); } int rek(int x, int y, int t) { int& out = num_ways[x][y][t]; if (out != -1) return out; out = 0; for (int z : ve[y]) { if (!inside(x, y, z, t)) continue; //cout << x + 1 << " " << y + 1 << " " << t << " -> " << z + 1 << endl; out = max(out, 1 + max(rek(y, z, 1 - t), rek(x, z, t))); } //cout << x + 1 << " " << y + 1 << " " << t << " --- " << out << endl; return out; } int main() { ios_base::sync_with_stdio(false); memset(num_ways, -1, sizeof num_ways); int n, k; cin >> n >> k; REP(i, n) { int x; cin >> x; while (x) { ve[i].push_back(x - 1); //cout << i << " " << x - 1 << endl; cin >> x; } } int out = 0, st = 0; REP(i, n) { for (int j : ve[i]) { int tr = 1 + max(rek(i, j, 1), rek(i, j, 0)); if (tr > out) { out = tr; st = i + 1; } //cout << i + 1 << " " << j + 1 << ": " << rek(i, j, 0) << " " << rek(i, j, 1) << endl; } } cout << out << "\n" << st << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...