oj.uz

Submission #525699

# Submission time Handle Problem Language Result Execution time Memory
525699 2022-02-12T15:16:07 Z Cantfindme Sailing Race (CEOI12_race) C++17
100 / 100
 930 ms 9652 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4300 KB Output is correct
2 Correct 2 ms 4428 KB Output is correct
3 Correct 2 ms 4428 KB Output is correct
4 Correct 3 ms 4556 KB Output is correct
5 Correct 3 ms 4428 KB Output is correct
6 Correct 5 ms 4684 KB Output is correct
7 Correct 5 ms 4428 KB Output is correct
8 Correct 6 ms 4832 KB Output is correct
9 Correct 5 ms 4428 KB Output is correct
10 Correct 13 ms 4556 KB Output is correct
11 Correct 7 ms 4428 KB Output is correct
12 Correct 60 ms 5884 KB Output is correct
13 Correct 104 ms 6904 KB Output is correct
14 Correct 51 ms 4640 KB Output is correct
15 Correct 600 ms 9112 KB Output is correct
16 Correct 772 ms 9468 KB Output is correct
17 Correct 594 ms 9068 KB Output is correct
18 Correct 73 ms 4668 KB Output is correct
19 Correct 928 ms 9648 KB Output is correct
20 Correct 930 ms 9652 KB Output is correct