oj.uz

Submission #237124

# Submission time Handle Problem Language Result Execution time Memory
237124 2020-06-04T17:39:28 Z mode149256 Race (IOI11_race) C++14
100 / 100
 1062 ms 58232 KB 
/*input

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

namespace my_template {
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}
}
using namespace my_template;

const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 200101;
const int DID = 1e6;

vb buvau(MX, false);
queue<int> toliau;
vi sz(MX);
int piv;
vi edges[MX];
vi len[MX];
int ats = MOD;
int reik;

vpi pir(DID + 1, {MOD, -1});
vpi ant(DID + 1, {MOD, -1});

vi visi;

int update(int x, int p) {
	piv++;
	sz[x] = 1;

	for (auto u : edges[x])
		if (!buvau[u] and u != p)
			sz[x] += update(u, x);

	return sz[x];
}

void prid(int x, int p, int curr, int cnt, int origin) {
	if (curr <= reik) {
		visi.emplace_back(curr);
		if (pir[curr].y == origin) {
			pir[curr].x = min(pir[curr].x, cnt);
		} else if (ant[curr].y == origin) {
			ant[curr].x = min(ant[curr].x, cnt);
			if (ant[curr] < pir[curr])
				swap(pir[curr], ant[curr]);
		} else {
			if (cnt <= pir[curr].x) {
				ant[curr] = pir[curr];
				pir[curr] = {cnt, origin};
			} else if (cnt < ant[curr].x) {
				ant[curr] = {cnt, origin};
			}
		}
	}

	for (int i = 0; i < (int)edges[x].size(); ++i)
	{
		int u = edges[x][i];
		if (!buvau[u] and u != p)
			prid(u, x, curr + len[x][i], cnt + 1, origin);
	}
}

void proccess(int x) {
	visi.clear();
	for (int i = 0; i < (int)edges[x].size(); ++i)
	{
		int u = edges[x][i];
		if (!buvau[u])
			prid(u, x, len[x][i], 1, u);
	}

	for (auto u : visi) {
		if (u > reik) continue;
		if (pir[u].y == -1 or pir[reik - u].y == -1) continue;

		if (pir[u].y != pir[reik - u].y) {
			// printf("u = %d, kit = %d, pir pir %d %d\n", u, reik - u, pir[u].x, pir[reik - u].x);
			ats = min(ats, pir[u].x + pir[reik - u].x);
		} else if (ant[reik - u].y != -1 and pir[u].y != ant[reik - u].y) {
			// printf("u = %d, kit = %d, pir ant %d %d\n", u, reik - u, pir[u].x, ant[reik - u].x);
			ats = min(ats, pir[u].x + ant[reik - u].x);
		} else if (ant[u].y != -1 and ant[u].y != pir[reik - u].y) {
			// printf("u = %d, kit = %d, ant pir %d %d\n", u, reik - u, ant[u].x, pir[reik - u].x);
			ats = min(ats, ant[u].x + pir[reik - u].x);
		}
		//  else if (ant[u].y != -1 and ant[reik - u].y != -1 and ant[u].y != ant[reik - u].y) {
		// 	ats = min(ats, ant[u].x + ant[reik - u].x);
		// }
	}

	for (auto u : visi) {
		pir[u] = ant[u] = {MOD, -1};
	}

	// for (int i = 0; i < (int)edges[x].size(); ++i)
	// {
	// 	int u = edges[x][i];
	// 	if (!buvau[u])
	// 		prid(u, x, len[x][i], -1, u);
	// }
}

void centroid(int x, int p, int dydis) {
	for (auto u : edges[x]) {
		if (!buvau[u] and u != p and sz[u] > dydis / 2) {
			centroid(u, x, dydis);
			return;
		}
	}

	// x is centroid
	proccess(x);
	buvau[x] = true;

	for (auto u : edges[x])
		if (!buvau[u])
			toliau.push(u);
}

int best_path(int N, int K, int H[][2], int L[])
{
	for (int i = 0; i < N - 1; ++i)
	{
		edges[H[i][0]].emplace_back(H[i][1]);
		len[H[i][0]].emplace_back(L[i]);
		edges[H[i][1]].emplace_back(H[i][0]);
		len[H[i][1]].emplace_back(L[i]);
	}

	pir[0] = {0, -5};
	reik = K;
	toliau.push(0);
	while (toliau.size()) {
		int c = toliau.front(); toliau.pop();

		piv = 0;
		update(c, -1);
		centroid(c, -1, piv);
	}

	if (ats == MOD) return -1;
	else return ats;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 26240 KB Output is correct
2 Correct 22 ms 26240 KB Output is correct
3 Correct 22 ms 26240 KB Output is correct
4 Correct 20 ms 26240 KB Output is correct
5 Correct 19 ms 26240 KB Output is correct
6 Correct 19 ms 26240 KB Output is correct
7 Correct 20 ms 26240 KB Output is correct
8 Correct 19 ms 26240 KB Output is correct
9 Correct 21 ms 26240 KB Output is correct
10 Correct 19 ms 26240 KB Output is correct
11 Correct 19 ms 26240 KB Output is correct
12 Correct 21 ms 26240 KB Output is correct
13 Correct 19 ms 26240 KB Output is correct
14 Correct 19 ms 26240 KB Output is correct
15 Correct 19 ms 26240 KB Output is correct
16 Correct 21 ms 26240 KB Output is correct
17 Correct 33 ms 26232 KB Output is correct
18 Correct 19 ms 26240 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 26240 KB Output is correct
2 Correct 22 ms 26240 KB Output is correct
3 Correct 22 ms 26240 KB Output is correct
4 Correct 20 ms 26240 KB Output is correct
5 Correct 19 ms 26240 KB Output is correct
6 Correct 19 ms 26240 KB Output is correct
7 Correct 20 ms 26240 KB Output is correct
8 Correct 19 ms 26240 KB Output is correct
9 Correct 21 ms 26240 KB Output is correct
10 Correct 19 ms 26240 KB Output is correct
11 Correct 19 ms 26240 KB Output is correct
12 Correct 21 ms 26240 KB Output is correct
13 Correct 19 ms 26240 KB Output is correct
14 Correct 19 ms 26240 KB Output is correct
15 Correct 19 ms 26240 KB Output is correct
16 Correct 21 ms 26240 KB Output is correct
17 Correct 33 ms 26232 KB Output is correct
18 Correct 19 ms 26240 KB Output is correct
19 Correct 19 ms 26240 KB Output is correct
20 Correct 21 ms 26240 KB Output is correct
21 Correct 20 ms 26240 KB Output is correct
22 Correct 20 ms 26240 KB Output is correct
23 Correct 20 ms 26240 KB Output is correct
24 Correct 20 ms 26240 KB Output is correct
25 Correct 20 ms 26368 KB Output is correct
26 Correct 20 ms 26240 KB Output is correct
27 Correct 20 ms 26240 KB Output is correct
28 Correct 20 ms 26368 KB Output is correct
29 Correct 21 ms 26368 KB Output is correct
30 Correct 21 ms 26368 KB Output is correct
31 Correct 21 ms 26368 KB Output is correct
32 Correct 20 ms 26368 KB Output is correct
33 Correct 20 ms 26368 KB Output is correct
34 Correct 21 ms 26240 KB Output is correct
35 Correct 20 ms 26368 KB Output is correct
36 Correct 20 ms 26368 KB Output is correct
37 Correct 21 ms 26368 KB Output is correct
38 Correct 21 ms 26240 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 26240 KB Output is correct
2 Correct 22 ms 26240 KB Output is correct
3 Correct 22 ms 26240 KB Output is correct
4 Correct 20 ms 26240 KB Output is correct
5 Correct 19 ms 26240 KB Output is correct
6 Correct 19 ms 26240 KB Output is correct
7 Correct 20 ms 26240 KB Output is correct
8 Correct 19 ms 26240 KB Output is correct
9 Correct 21 ms 26240 KB Output is correct
10 Correct 19 ms 26240 KB Output is correct
11 Correct 19 ms 26240 KB Output is correct
12 Correct 21 ms 26240 KB Output is correct
13 Correct 19 ms 26240 KB Output is correct
14 Correct 19 ms 26240 KB Output is correct
15 Correct 19 ms 26240 KB Output is correct
16 Correct 21 ms 26240 KB Output is correct
17 Correct 33 ms 26232 KB Output is correct
18 Correct 19 ms 26240 KB Output is correct
19 Correct 327 ms 35252 KB Output is correct
20 Correct 317 ms 35064 KB Output is correct
21 Correct 360 ms 35320 KB Output is correct
22 Correct 292 ms 35832 KB Output is correct
23 Correct 226 ms 35064 KB Output is correct
24 Correct 127 ms 35576 KB Output is correct
25 Correct 261 ms 39160 KB Output is correct
26 Correct 136 ms 43384 KB Output is correct
27 Correct 410 ms 43880 KB Output is correct
28 Correct 735 ms 58232 KB Output is correct
29 Correct 757 ms 56696 KB Output is correct
30 Correct 409 ms 43256 KB Output is correct
31 Correct 425 ms 43256 KB Output is correct
32 Correct 634 ms 43508 KB Output is correct
33 Correct 698 ms 42104 KB Output is correct
34 Correct 599 ms 42104 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 26240 KB Output is correct
2 Correct 22 ms 26240 KB Output is correct
3 Correct 22 ms 26240 KB Output is correct
4 Correct 20 ms 26240 KB Output is correct
5 Correct 19 ms 26240 KB Output is correct
6 Correct 19 ms 26240 KB Output is correct
7 Correct 20 ms 26240 KB Output is correct
8 Correct 19 ms 26240 KB Output is correct
9 Correct 21 ms 26240 KB Output is correct
10 Correct 19 ms 26240 KB Output is correct
11 Correct 19 ms 26240 KB Output is correct
12 Correct 21 ms 26240 KB Output is correct
13 Correct 19 ms 26240 KB Output is correct
14 Correct 19 ms 26240 KB Output is correct
15 Correct 19 ms 26240 KB Output is correct
16 Correct 21 ms 26240 KB Output is correct
17 Correct 33 ms 26232 KB Output is correct
18 Correct 19 ms 26240 KB Output is correct
19 Correct 19 ms 26240 KB Output is correct
20 Correct 21 ms 26240 KB Output is correct
21 Correct 20 ms 26240 KB Output is correct
22 Correct 20 ms 26240 KB Output is correct
23 Correct 20 ms 26240 KB Output is correct
24 Correct 20 ms 26240 KB Output is correct
25 Correct 20 ms 26368 KB Output is correct
26 Correct 20 ms 26240 KB Output is correct
27 Correct 20 ms 26240 KB Output is correct
28 Correct 20 ms 26368 KB Output is correct
29 Correct 21 ms 26368 KB Output is correct
30 Correct 21 ms 26368 KB Output is correct
31 Correct 21 ms 26368 KB Output is correct
32 Correct 20 ms 26368 KB Output is correct
33 Correct 20 ms 26368 KB Output is correct
34 Correct 21 ms 26240 KB Output is correct
35 Correct 20 ms 26368 KB Output is correct
36 Correct 20 ms 26368 KB Output is correct
37 Correct 21 ms 26368 KB Output is correct
38 Correct 21 ms 26240 KB Output is correct
39 Correct 327 ms 35252 KB Output is correct
40 Correct 317 ms 35064 KB Output is correct
41 Correct 360 ms 35320 KB Output is correct
42 Correct 292 ms 35832 KB Output is correct
43 Correct 226 ms 35064 KB Output is correct
44 Correct 127 ms 35576 KB Output is correct
45 Correct 261 ms 39160 KB Output is correct
46 Correct 136 ms 43384 KB Output is correct
47 Correct 410 ms 43880 KB Output is correct
48 Correct 735 ms 58232 KB Output is correct
49 Correct 757 ms 56696 KB Output is correct
50 Correct 409 ms 43256 KB Output is correct
51 Correct 425 ms 43256 KB Output is correct
52 Correct 634 ms 43508 KB Output is correct
53 Correct 698 ms 42104 KB Output is correct
54 Correct 599 ms 42104 KB Output is correct
55 Correct 30 ms 27136 KB Output is correct
56 Correct 31 ms 27256 KB Output is correct
57 Correct 134 ms 35064 KB Output is correct
58 Correct 65 ms 35944 KB Output is correct
59 Correct 135 ms 42680 KB Output is correct
60 Correct 841 ms 57460 KB Output is correct
61 Correct 441 ms 45816 KB Output is correct
62 Correct 463 ms 46368 KB Output is correct
63 Correct 667 ms 46452 KB Output is correct
64 Correct 1062 ms 45936 KB Output is correct
65 Correct 758 ms 45572 KB Output is correct
66 Correct 966 ms 56476 KB Output is correct
67 Correct 269 ms 47584 KB Output is correct
68 Correct 664 ms 46796 KB Output is correct
69 Correct 595 ms 47268 KB Output is correct
70 Correct 529 ms 46072 KB Output is correct