Submission #410038

#	Time	Username	Problem	Language	Result	Execution time	Memory
410038		LucaDantas	Rail (IOI14_rail)	C++17	30 / 100	98 ms	19416 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)((a).size())

constexpr int maxn = 5010;

bool mark[maxn], lado[maxn];

int dp[maxn][maxn];

int dist(int a, int b) { return dp[a][b] ? dp[a][b] : dp[a][b] = getDistance(a, b); }

void findLocation(int N, int first, int location[], int stype[])
{
	int menor = 0, d = 0x3f3f3f3f;
	for(int i = 1; i < N; i++)
		if(dist(0, i) < d) menor = i, d = dist(0, i);
	location[0] = first; stype[0] = 1;
	location[menor] = first + d; stype[menor] = 2;
	vector<int> l, r;

	for(int i = 1; i < N; i++) {
		if(i == menor) continue;
		if(dist(0, i) == d + dist(menor, i)) l.pb(i);
		else r.pb(i), lado[i] = 1;
	}
	
	sort(all(l), [](int x, int y) { return dp[0][x] < dp[0][y]; });
	sort(all(r), [](int x, int y) { return dp[0][x] < dp[0][y]; });

	// printf("%d %d\n", sz(l), sz(r));
	
	for(int i = 0; i < sz(r);) {
		location[r[i]] = location[0] + dist(0, r[i]); stype[r[i]] = 2;
		// printf("r %d\n", r[i]);
		int j = i+1;
		for(; dist(0, r[j]) == dist(0, r[i]) + dist(r[i], r[j]) && j < sz(r); j++)
			location[r[j]] = location[r[i]] - dist(r[i], r[j]), stype[r[j]] = 1;
		i = j;
	}
	
	for(int i = 0; i < sz(l);) {
		location[l[i]] = location[menor] - dist(menor, l[i]); stype[l[i]] = 1;
		// printf("l %d\n", l[i]);
		int j = i+1;
		for(; dist(menor, l[j]) == dist(menor, l[i]) + dist(l[i], l[j]) && j < sz(l); j++)
			location[l[j]] = location[l[i]] + dist(l[i], l[j]), stype[l[j]] = 2;
		i = j;
	}
	
	// for(int i = 0; i < N; i++)
	// 	printf("%d ", location[i]);
	// puts("");
	// for(int i = 0; i < N; i++)
	// 	printf("%d ", stype[i]);
	// puts("");
}

• Subtask 1: 8 / 8
• Subtask 2: 22 / 22
• Subtask 3: 0 / 26
• Subtask 4: 0 / 44