Submission #979193

#TimeUsernameProblemLanguageResultExecution timeMemory
979193NonozeSailing Race (CEOI12_race)C++17
40 / 100
401 ms14928 KiB
/* * Author: Nonoze * Created: Friday 10/05/2024 */ #include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long ll; #define int long long #ifdef _IN_LOCAL #include <bits/DebugTemplate.h> #else #define dbg(...) #endif #define sz(x) (int)(x.size()) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define pb push_back #define mp make_pair #define fi first #define se second template<typename T> void read(T& x, bool write=0) { if (write) cout << x << ' '; else cin >> x; } template<typename T1, typename T2> void read(pair<T1, T2>& p, bool write=0) { read(p.first, write), read(p.second, write); if (write) cout << endl;} template<typename T> void read(vector<T>& v, bool write=0) { for (auto& x : v) read(x, write); if (write) cout << endl; } template<typename T1, typename T2> void read(T1& x, T2& y, bool write=0) { read(x, write), read(y, write); if (write) cout << endl; } template<typename T1, typename T2, typename T3> void read(T1& x, T2& y, T3& z, bool write=0) { read(x, write), read(y, write), read(z, write); if (write) cout << endl; } template<typename T> void print(T x) { read(x, 1); cout << endl; } template<typename T1, typename T2> void print(T1 x, T2 y) { read(x, y, 1); } template<typename T1, typename T2, typename T3> void print(T1 x, T2 y, T3 z) { read(x, y, z, 1); } #define endl '\n' #define endlfl '\n' << flush #define quit(x) {cout << x << endl; return;} #define cmin(a, b) a = min(a, b) #define cmax(a, b) a = max(a, b) const int inf = numeric_limits<int>::max() / 4; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int MOD = 1e9+7, LOG=25; void solve(); signed main() { ios::sync_with_stdio(0); cin.tie(0); int tt=1; // cin >> tt; while(tt--) solve(); return 0; } int n, k, m, q; vector<vector<int>> adj; vector<vector<vector<int>>> memo; bool valable(int node, int left, int right) { if (node>left && node<right) return 1; if (right<left && (node>left || node<right)) return 1; return 0; } int dp(int l, int r, bool left) { if (memo[l][r][left]!=-1) return memo[l][r][left]; int u=(left?l:r); int ans=0; for (auto v: adj[u]) { if (valable(v, l, r)) { cmax(ans, dp(v, r, 1)); cmax(ans, dp(l, v, 0)); } } return memo[l][r][left]=ans+1; } void solve() { read(n, k); adj.resize(n); for (int i=0; i<n; i++) { int x; read(x); while (x!=0) { x--; adj[i].pb(x); read(x); } } memo.resize(n, vector<vector<int>>(n, vector<int>(2, -1))); int ans=0, empl=0; for (int i=0; i<n; i++) { int act=0; for (auto v: adj[i]) { cmax(act, dp(i, v, 0)); cmax(act, dp(v, i, 1)); } if (act>ans) { ans=act; empl=i; } } print(ans); print(empl+1); }
#Verdict Execution timeMemoryGrader output
Fetching results...