Submission #525699

#	Time	Username	Problem	Language	Result	Execution time	Memory
525699		Cantfindme	Sailing Race (CEOI12_race)	C++17	100 / 100	930 ms	9652 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()
typedef pair<int, pi> pii;
#define ld long double

const int maxn = 510;
const int INF = LLONG_MAX/2;
const int mod = 1e9+7;

int dp[maxn][maxn][2];
int dist[maxn][maxn][2]; //Best answer to go from i to j, clockwise or anticlockwise
vector <int> adjlist[maxn];
vector <int> backlist[maxn];
int n, K;

int dpf(int x, int jumps, int dir) {
	if (dp[x][jumps][dir] != -1) return dp[x][jumps][dir];
	int res = 0, need = 0;
	
	for (auto i: adjlist[x]) {
		if (dir == 1) {
			need = (i - x + n) % n;
		} else {
			need = (x - i + n) % n;
		}
		if (need > jumps) continue;
		res = max(res, dpf(i, jumps - need, dir) + 1);
		res = max(res, dpf(i, need - 1, !dir) + 1);
	}
	
	return dp[x][jumps][dir] = res;
}

int SSS;
bool cmp(int a, int b) {
	return (a - SSS + n) % n < (b - SSS + n) % n;
}

bool cmp2(int a, int b) {
	return (a - SSS + n) % n > (b - SSS + n) % n;
}

int32_t main() {
	FAST
	// #ifndef ONLINE_JUDGE
	// 	ifstream cin("input.txt");
	// #endif

	cin >> n >> K;
	for (int i =0;i<n;i++) {
		while (true) {
			int x; cin >> x;
			if (x == 0) break;
			x--;

			backlist[x].push_back(i);
			adjlist[i].push_back(x);
		}
	}
	
	pi rans = pi(0,1);
	memset(dp,-1,sizeof dp);
	
	for (int i =0;i<n;i++) {
		rans = max(rans, pi(dpf(i, n-1, 1), i)); //1 is anticlockwise
	}
	
	if (K == 0) {
		cout << rans.f << "\n" << rans.s + 1;
		return 0;
	} 

	//Solve for K = 1

	//Find best distance between a fixed start and X node
	for (int s = 0; s < n; s++) {
		int x = s;
		for (auto i: adjlist[x]) {
			dist[s][i][1] = 1;
		}
		x = (x + 1) % n;
		while (x != s) {
			int d = dist[s][x][1];
			if (d == 0) goto skip1;

			for (auto i: adjlist[x]) {
				if ((i - s + n) % n > (x - s + n) % n) dist[s][i][1] = max(dist[s][i][1], d + 1);
			}

			skip1:;
			x = (x + 1) % n;
		}

		x = s;
		for (auto i: adjlist[x]) dist[s][i][0] = 1;
		x = (x - 1 + n) % n;
		while (x != s) {
			int d = dist[s][x][0];
			if (d == 0) goto skip2;

			for (auto i: adjlist[x]) {
				if ((i - s + n) % n < (x - s + n) % n)
					dist[s][i][0] = max(dist[s][i][0], d + 1);
			}

			skip2:;
			x = (x - 1 + n) % n;
		}
	}

	for (int s = 0; s < n; s++) {
		SSS = s;
		sort(all(backlist[s]), cmp);
		if (backlist[s].empty()) continue;
		int pp = 0;

		for (int x = (s + 1) % n; x != s; x = (x + 1) % n) {
			if ((backlist[s][pp]-s+n)%n <= (x - s + n)%n) {
				pp++;
			}
			if (pp >= backlist[s].size()) break;
			if (dist[s][x][1] == 0) continue;
			int TT = backlist[s][pp];

			for (auto j : adjlist[x]) {
				if ((j - s + n) % n <= (TT - s + n) % n) continue;
				int jumps = n - ((j-s+n)%n) - 1;
				int jumps2 = (j - s + n) % n - (TT-s+n)%n - 1;
				int res = max(dpf(j, jumps, 1), dpf(j, jumps2, 0));

				// cout << 1 << " s:" << s << " x:" << x << " T:" << TT << " j:" << j << " " << dist[s][x][1] + res + 2 << "\n";
				rans = max(rans, pi(dist[s][x][1] + res + 2,TT));	
			}
		}

		sort(all(backlist[s]), cmp2);
		pp = 0;
		
		for (int x = (s - 1 + n) % n; x != s; x = (x - 1 + n) % n) {
			if ((backlist[s][pp]-s+n)%n >= (x - s + n)%n) {
				pp++;
			}
			if (pp >= backlist[s].size()) break;
			if (dist[s][x][0] == 0) continue;
			int TT = backlist[s][pp];

			for (auto j : adjlist[x]) {
				if (j == s or (j - s + n) % n >= (TT - s + n) % n) continue;
				int jumps = (j-s+n)%n - 1;
				int jumps2 = (TT-s+n)%n - (j-s+n)%n - 1;
				int res = max(dpf(j,jumps,0), dpf(j,jumps2,1));

				// cout << 0 << " s:" << s << " x:" << x << " T:" << TT << " j:" << j << " " << dist[s][x][0] + res + 2 << "\n";
				rans = max(rans, pi(dist[s][x][0] + res + 2,TT));	
			}
		}
	}

	cout << rans.f << "\n" << rans.s + 1;
}

Compilation message (stderr)

race.cpp: In function 'int32_t main()':
race.cpp:127:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |    if (pp >= backlist[s].size()) break;
      |        ~~~^~~~~~~~~~~~~~~~~~~~~
race.cpp:149:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |    if (pp >= backlist[s].size()) break;
      |        ~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100