oj.uz

Submission #1100484

# Submission time Handle Problem Language Result Execution time Memory
1100484 2024-10-14T04:54:47 Z sssamui Race (IOI11_race) C++17
9 / 100
 82 ms 27516 KB 
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
#include <algorithm>
using namespace std;
using ll = long long;

const int MXN = 2e5;

vector<vector<pair<int, ll>>> adj(MXN, vector<pair<int, ll>>(0));

vector<int> dep(MXN, 0);
vector<ll> dtr(MXN, 0);
vector<set<pair<ll, int>>> tmerg(MXN);

int ans = MXN;
int k;

void dfs(int node = 0, int p = -1)
{
	tmerg[node].insert({ dtr[node], dep[node] });
	for (pair<int, ll> nxt : adj[node]) if (nxt.first != p)
	{
		dep[nxt.first] = dep[node] + 1, dtr[nxt.first] = dtr[node] + nxt.second;
		dfs(nxt.first, node);

		bool cont = true;
		while ((!tmerg[nxt.first].empty()) && cont)
		{
			auto it = tmerg[nxt.first].end();
			it--;
			if ((*it).first - dtr[node] < k) cont = false;
			else
			{
				if ((*it).first - dtr[node] == k) ans = fmin(ans, (*it).second - dep[node]);
				tmerg[nxt.first].erase(it);
			}
		}

		if (tmerg[node].size() < tmerg[nxt.first].size()) swap(tmerg[node], tmerg[nxt.first]);
		for (pair<ll, int> tins : tmerg[nxt.first])
		{
			ll finddep = k - tins.first + 2 * dtr[node];
			auto it = tmerg[nxt.first].lower_bound({ finddep, 0 });
			if ((it != tmerg[nxt.first].end()) && ((*it).first == finddep)) ans = fmin(ans, (*it).second - 2 * dep[node] + tins.second);
		}

		for (pair<ll, int> tins : tmerg[nxt.first])
		{
			auto it = tmerg[node].lower_bound(tins);
			while ((it != tmerg[node].end()) && ((*it).first == tins.first))
			{
				tmerg[node].erase(it);
				it = tmerg[node].lower_bound(tins);
			}

			bool ins = true;
			if (it != tmerg[node].begin())
			{
				it--;
				if ((*it).first == tins.first) ins = false;
			}

			if (ins) tmerg[node].insert(tins);
		}

		tmerg[nxt.first].clear();
	}
}

int best_path(int N, int K, int H[][2], int L[])
{
	k = K;
	for (int i = 0; i < N - 1; i++) adj[H[i][0]].push_back({ H[i][1], L[i] }), adj[H[i][1]].push_back({ H[i][0], L[i] });
	dfs();
	if (ans == MXN) return -1;
	else return ans;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 18768 KB Output is correct
2 Correct 6 ms 18780 KB Output is correct
3 Correct 5 ms 18940 KB Output is correct
4 Correct 5 ms 18732 KB Output is correct
5 Correct 6 ms 18768 KB Output is correct
6 Correct 6 ms 18932 KB Output is correct
7 Correct 5 ms 18780 KB Output is correct
8 Correct 5 ms 18768 KB Output is correct
9 Correct 7 ms 18768 KB Output is correct
10 Correct 6 ms 18780 KB Output is correct
11 Correct 6 ms 18764 KB Output is correct
12 Correct 6 ms 18768 KB Output is correct
13 Correct 5 ms 18776 KB Output is correct
14 Correct 6 ms 18780 KB Output is correct
15 Correct 6 ms 18768 KB Output is correct
16 Correct 5 ms 18780 KB Output is correct
17 Correct 6 ms 18780 KB Output is correct
18 Correct 5 ms 18912 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 18768 KB Output is correct
2 Correct 6 ms 18780 KB Output is correct
3 Correct 5 ms 18940 KB Output is correct
4 Correct 5 ms 18732 KB Output is correct
5 Correct 6 ms 18768 KB Output is correct
6 Correct 6 ms 18932 KB Output is correct
7 Correct 5 ms 18780 KB Output is correct
8 Correct 5 ms 18768 KB Output is correct
9 Correct 7 ms 18768 KB Output is correct
10 Correct 6 ms 18780 KB Output is correct
11 Correct 6 ms 18764 KB Output is correct
12 Correct 6 ms 18768 KB Output is correct
13 Correct 5 ms 18776 KB Output is correct
14 Correct 6 ms 18780 KB Output is correct
15 Correct 6 ms 18768 KB Output is correct
16 Correct 5 ms 18780 KB Output is correct
17 Correct 6 ms 18780 KB Output is correct
18 Correct 5 ms 18912 KB Output is correct
19 Correct 5 ms 18776 KB Output is correct
20 Correct 6 ms 18956 KB Output is correct
21 Correct 6 ms 19036 KB Output is correct
22 Incorrect 7 ms 18784 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 18768 KB Output is correct
2 Correct 6 ms 18780 KB Output is correct
3 Correct 5 ms 18940 KB Output is correct
4 Correct 5 ms 18732 KB Output is correct
5 Correct 6 ms 18768 KB Output is correct
6 Correct 6 ms 18932 KB Output is correct
7 Correct 5 ms 18780 KB Output is correct
8 Correct 5 ms 18768 KB Output is correct
9 Correct 7 ms 18768 KB Output is correct
10 Correct 6 ms 18780 KB Output is correct
11 Correct 6 ms 18764 KB Output is correct
12 Correct 6 ms 18768 KB Output is correct
13 Correct 5 ms 18776 KB Output is correct
14 Correct 6 ms 18780 KB Output is correct
15 Correct 6 ms 18768 KB Output is correct
16 Correct 5 ms 18780 KB Output is correct
17 Correct 6 ms 18780 KB Output is correct
18 Correct 5 ms 18912 KB Output is correct
19 Incorrect 82 ms 27516 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 18768 KB Output is correct
2 Correct 6 ms 18780 KB Output is correct
3 Correct 5 ms 18940 KB Output is correct
4 Correct 5 ms 18732 KB Output is correct
5 Correct 6 ms 18768 KB Output is correct
6 Correct 6 ms 18932 KB Output is correct
7 Correct 5 ms 18780 KB Output is correct
8 Correct 5 ms 18768 KB Output is correct
9 Correct 7 ms 18768 KB Output is correct
10 Correct 6 ms 18780 KB Output is correct
11 Correct 6 ms 18764 KB Output is correct
12 Correct 6 ms 18768 KB Output is correct
13 Correct 5 ms 18776 KB Output is correct
14 Correct 6 ms 18780 KB Output is correct
15 Correct 6 ms 18768 KB Output is correct
16 Correct 5 ms 18780 KB Output is correct
17 Correct 6 ms 18780 KB Output is correct
18 Correct 5 ms 18912 KB Output is correct
19 Correct 5 ms 18776 KB Output is correct
20 Correct 6 ms 18956 KB Output is correct
21 Correct 6 ms 19036 KB Output is correct
22 Incorrect 7 ms 18784 KB Output isn't correct
23 Halted 0 ms 0 KB -