oj.uz

답안 #525697

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
525697 2022-02-12T15:03:37 Z Cantfindme Sailing Race (CEOI12_race) C++17
75 / 100
 901 ms 9820 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) {
			if (i > x) need = i - x;
			else need = n - x + i;
		} else {
			if (i < x) need = x - i;
			else need = x + n - i;
		}
		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,0);
	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;
		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:129: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]
  129 |    if (pp >= backlist[s].size()) break;
      |        ~~~^~~~~~~~~~~~~~~~~~~~~
race.cpp:151: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]
  151 |    if (pp >= backlist[s].size()) break;
      |        ~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
75.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4308 KB Output is correct
2 Correct 3 ms 4428 KB Output is correct
3 Correct 3 ms 4436 KB Output is correct
4 Correct 3 ms 4556 KB Output is correct
5 Incorrect 7 ms 4428 KB Output isn't correct
6 Correct 5 ms 4696 KB Output is correct
7 Correct 4 ms 4428 KB Output is correct
8 Correct 5 ms 4812 KB Output is correct
9 Incorrect 5 ms 4448 KB Output isn't correct
10 Correct 9 ms 4680 KB Output is correct
11 Incorrect 5 ms 4556 KB Output isn't correct
12 Correct 52 ms 6016 KB Output is correct
13 Correct 91 ms 7060 KB Output is correct
14 Incorrect 49 ms 4684 KB Output isn't correct
15 Correct 549 ms 9260 KB Output is correct
16 Correct 714 ms 9620 KB Output is correct
17 Correct 543 ms 9248 KB Output is correct
18 Incorrect 49 ms 4704 KB Output isn't correct
19 Correct 895 ms 9820 KB Output is correct
20 Correct 901 ms 9816 KB Output is correct