oj.uz

Submission #979193

# Submission time Handle Problem Language Result Execution time Memory
979193 2024-05-10T11:11:13 Z Nonoze Sailing Race (CEOI12_race) C++17
40 / 100
 401 ms 14928 KB 
/*
*	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);
}

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 344 KB Output isn't correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Correct 1 ms 600 KB Output is correct
6 Incorrect 1 ms 600 KB Output isn't correct
7 Correct 3 ms 604 KB Output is correct
8 Incorrect 3 ms 756 KB Output isn't correct
9 Correct 4 ms 728 KB Output is correct
10 Correct 11 ms 1160 KB Output is correct
11 Correct 6 ms 860 KB Output is correct
12 Incorrect 20 ms 2776 KB Output isn't correct
13 Incorrect 41 ms 5544 KB Output isn't correct
14 Correct 66 ms 9308 KB Output is correct
15 Incorrect 262 ms 14372 KB Output isn't correct
16 Incorrect 330 ms 14684 KB Output isn't correct
17 Incorrect 263 ms 14428 KB Output isn't correct
18 Correct 106 ms 14172 KB Output is correct
19 Incorrect 401 ms 14872 KB Output isn't correct
20 Incorrect 356 ms 14928 KB Output isn't correct