oj.uz

Submission #908150

# Submission time Handle Problem Language Result Execution time Memory
908150 2024-01-16T08:45:13 Z ono_de206 Rail (IOI14_rail) C++14
100 / 100
 109 ms 99048 KB 
#include "rail.h"
#include<bits/stdc++.h>
using namespace std;

#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

//#define int long long

typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

void findLocation(int n, int first, int pos[], int tp[]) {
	pos[0] = first;
	tp[0] = 1;

	if(n == 1) return;

	vector<vector<int>> dis(n, vector<int>(n, -1));

	auto get = [&](int x, int y) -> int {
		if(x > y) swap(x, y);
		if(dis[x][y] != -1) return dis[x][y];
		return dis[x][y] = getDistance(x, y);
	};

	vector<int> id(n - 1);
	iota(all(id), 1);
	sort(all(id), [&](int x, int y) {
		return get(0, x) < get(0, y);
	});

	map<int, int> mp;

	int l = id[0], k = id[0];

	pos[l] = pos[0] + get(0, l);
	tp[l] = 2;

	id.erase(id.begin());

	mp[pos[0]] = tp[0];
	mp[pos[k]] = tp[k];

	for(int x : id) {
		if(get(0, k) + get(k, x) != get(0, x)) {
			int gg = pos[l] - (get(0, l) + get(l, x) - get(0, x)) / 2;
			if(mp[gg] == 2) {
				pos[x] = pos[l] - get(l, x);
				tp[x] = 1;
			} else {
				pos[x] = pos[0] + get(0, x);
				tp[x] = 2;
				l = x;
			}
			mp[pos[x]] = tp[x];
		}
	}
	id.resize(n - 1);
	iota(all(id), 1);
	id.erase(find(all(id), k));
	sort(all(id), [&](int x, int y) {
		return get(k, x) < get(k, y);
	});

	l = 0;

	for(int x : id) {
		if(get(0, k) + get(k, x) == get(0, x)) {
			int gg = pos[l] + (get(k, l) + get(l, x) - get(k, x)) / 2;
			if(mp[gg] == 1) {
				pos[x] = pos[l] + get(l, x);
				tp[x] = 2;
			} else {
				pos[x] = pos[k] - get(k, x);
				tp[x] = 1;
				l = x;
			}
			mp[pos[x]] = tp[x];
		}
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 516 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 412 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 98648 KB Output is correct
2 Correct 93 ms 98788 KB Output is correct
3 Correct 93 ms 98700 KB Output is correct
4 Correct 95 ms 98724 KB Output is correct
5 Correct 93 ms 98896 KB Output is correct
6 Correct 94 ms 98896 KB Output is correct
7 Correct 93 ms 98900 KB Output is correct
8 Correct 95 ms 99048 KB Output is correct
9 Correct 92 ms 98920 KB Output is correct
10 Correct 94 ms 98868 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 98804 KB Output is correct
2 Correct 95 ms 98848 KB Output is correct
3 Correct 92 ms 98820 KB Output is correct
4 Correct 93 ms 98828 KB Output is correct
5 Correct 92 ms 98676 KB Output is correct
6 Correct 93 ms 98900 KB Output is correct
7 Correct 95 ms 98692 KB Output is correct
8 Correct 93 ms 98900 KB Output is correct
9 Correct 96 ms 98900 KB Output is correct
10 Correct 93 ms 98816 KB Output is correct
11 Correct 95 ms 98700 KB Output is correct
12 Correct 93 ms 98700 KB Output is correct
13 Correct 93 ms 98900 KB Output is correct
14 Correct 109 ms 98680 KB Output is correct
15 Correct 93 ms 98824 KB Output is correct
16 Correct 94 ms 98692 KB Output is correct
17 Correct 94 ms 98900 KB Output is correct
18 Correct 106 ms 98692 KB Output is correct
19 Correct 93 ms 98896 KB Output is correct
20 Correct 91 ms 98700 KB Output is correct