oj.uz

Submission #147513

# Submission time Handle Problem Language Result Execution time Memory
147513 2019-08-29T22:16:29 Z faremy Highway Tolls (IOI18_highway) C++14
51 / 100
 285 ms 17292 KB 
#include "highway.h"

#include <queue>
#include <algorithm>


struct Edge
{
	Edge(int d, int i) : dest(d), id(i) {}
	int dest, id;

	bool operator ==(const Edge &other) const
	{
		return (dest == other.dest && id == other.id);
	}
};

const int MAXN = 90000;

std::vector<Edge> graph[MAXN];
std::vector<int> trafficCondition;

std::queue<int> bfs;
std::vector<Edge> tree[MAXN];
int parent[MAXN], parentEdge[MAXN];

std::vector<int> opti;


inline void set0(int road)
{
	trafficCondition[road] = 0;
}

inline void set1(int road)
{
	trafficCondition[road] = 1;
}

inline void toogle(int road)
{
	trafficCondition[road] = 1 - trafficCondition[road];
}

int findroot(int left, int right, long long expectedLength)
{
	if (left == right)
		return MAXN;
	int middle = (left + right) / 2;

	for (int iNode = 0; iNode <= middle; iNode++)
		for (Edge &edge : graph[iNode])
			set1(edge.id);

	long long shortestPath = ask(trafficCondition);
	for (int iNode = 0; iNode <= middle; iNode++)
		for (Edge &edge : graph[iNode])
			set0(edge.id);
	
	if (shortestPath > expectedLength)
		return std::min(middle, findroot(left, middle, expectedLength));
	return findroot(middle + 1, right, expectedLength);
}

void buildtree(int root)
{
	bfs.emplace(root);
	parent[root] = -1;
	
	std::fill_n(parentEdge, MAXN, -1);
	parentEdge[root] = -2;

	while (!bfs.empty())
	{
		int node = bfs.front();
		bfs.pop();

		for (Edge &edge : graph[node])
			if (parentEdge[edge.dest] == -1)
			{
				tree[node].emplace_back(edge);
				parent[edge.dest] = node;
				parentEdge[edge.dest] = edge.id;
				
				set1(edge.id);
				bfs.emplace(edge.dest);
			}
	}
}

void toogledepth(int node, int depth, int maxDepth)
{
	if (depth == maxDepth)
		return;
	
	for (Edge &edge : tree[node])
	{
		toogle(edge.id);
		toogledepth(edge.dest, depth + 1, maxDepth);
	}
}

void makedepthset(int node, std::vector<int> &nodeSet, int depth, int maxDepth)
{
	if (depth == maxDepth)
	{
		nodeSet.emplace_back(node);
		return;
	}

	for (Edge &edge : tree[node])
		makedepthset(edge.dest, nodeSet, depth + 1, maxDepth);
}

int searchextremity(std::vector<int> candidates, long long expectedLength, long long whenUpd)
{
	if (candidates.size() == 1)
		return candidates[0];

	for (int iNode = 0; iNode < (int)candidates.size() / 2; iNode++)
		set1(parentEdge[candidates[iNode]]);

	long long shortestPath = ask(trafficCondition);
	for (int iNode = 0; iNode < (int)candidates.size() / 2; iNode++)
		set0(parentEdge[candidates[iNode]]);

	if (shortestPath == expectedLength + whenUpd)
	{
		opti = std::vector<int>(candidates.begin() + candidates.size() / 2, candidates.end());
		return searchextremity(std::vector<int>(candidates.begin(), candidates.begin() + candidates.size() / 2), expectedLength, -1);
	}

	if (shortestPath > expectedLength)
		return searchextremity(std::vector<int>(candidates.begin(), candidates.begin() + candidates.size() / 2), expectedLength, whenUpd);
	return searchextremity(std::vector<int>(candidates.begin() + candidates.size() / 2, candidates.end()), expectedLength, whenUpd);
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B)
{
	for (int iEdge = 0; iEdge < (int)U.size(); iEdge++)
	{
		graph[U[iEdge]].emplace_back(V[iEdge], iEdge);
		graph[V[iEdge]].emplace_back(U[iEdge], iEdge);
	}

	trafficCondition.resize(U.size(), 0);
	long long shortestPath = ask(trafficCondition);
	long long edgesOnPath = shortestPath / (long long)A;

	int root = findroot(0, N, shortestPath);
	buildtree(root);

	for (int i = 0; i < (int)U.size(); i++)
		toogle(i);
	toogledepth(root, 0, edgesOnPath / 2);
	long long newShort = ask(trafficCondition);
	toogledepth(root, 0, edgesOnPath / 2);

	if (newShort == edgesOnPath * (long long)B)
	{
		std::vector<int> nodes;
		makedepthset(root, nodes, 0, edgesOnPath / 2);
		int s = searchextremity(nodes, shortestPath, B - A);
		int t = searchextremity(opti, shortestPath, -1);
		answer(s, t);
	}
	else
	{
		long long Sdepth = (newShort - shortestPath - (edgesOnPath / 2LL) * (long long)(B - A)) / (long long)(B - A);
		std::vector<int> nodes;
		makedepthset(root, nodes, 0, edgesOnPath - Sdepth);
		int t = searchextremity(nodes, shortestPath, -1);

		int block = t;
		while (parent[block] != -1)
		{
			tree[parent[block]].erase(std::find(tree[parent[block]].begin(), tree[parent[block]].end(), Edge(block, parentEdge[block])));
			block = parent[block];
		}

		nodes.clear();
		makedepthset(root, nodes, 0, Sdepth);
		int s = searchextremity(nodes, shortestPath, -1);
		answer(s, t);
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4856 KB Output is correct
2 Correct 6 ms 4856 KB Output is correct
3 Correct 6 ms 4884 KB Output is correct
4 Correct 6 ms 4856 KB Output is correct
5 Correct 7 ms 4856 KB Output is correct
6 Correct 6 ms 4796 KB Output is correct
7 Correct 6 ms 4856 KB Output is correct
8 Correct 7 ms 4856 KB Output is correct
9 Correct 6 ms 4856 KB Output is correct
10 Correct 7 ms 4856 KB Output is correct
11 Correct 6 ms 4796 KB Output is correct
12 Correct 7 ms 4856 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4928 KB Output is correct
2 Correct 26 ms 5752 KB Output is correct
3 Correct 208 ms 12120 KB Output is correct
4 Correct 201 ms 12184 KB Output is correct
5 Correct 228 ms 12240 KB Output is correct
6 Correct 225 ms 12032 KB Output is correct
7 Correct 217 ms 12168 KB Output is correct
8 Correct 223 ms 12168 KB Output is correct
9 Correct 212 ms 12028 KB Output is correct
10 Correct 216 ms 12168 KB Output is correct
11 Correct 220 ms 12852 KB Output is correct
12 Correct 222 ms 13304 KB Output is correct
13 Correct 207 ms 13152 KB Output is correct
14 Correct 230 ms 13408 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 5752 KB Output is correct
2 Correct 44 ms 6704 KB Output is correct
3 Correct 68 ms 7492 KB Output is correct
4 Correct 186 ms 13596 KB Output is correct
5 Correct 177 ms 12668 KB Output is correct
6 Correct 180 ms 16164 KB Output is correct
7 Correct 201 ms 12712 KB Output is correct
8 Correct 173 ms 14624 KB Output is correct
9 Correct 184 ms 12756 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4856 KB Output is correct
2 Correct 28 ms 5628 KB Output is correct
3 Correct 198 ms 10492 KB Output is correct
4 Correct 285 ms 12104 KB Output is correct
5 Correct 209 ms 11964 KB Output is correct
6 Correct 228 ms 12056 KB Output is correct
7 Correct 221 ms 11964 KB Output is correct
8 Correct 229 ms 12000 KB Output is correct
9 Correct 224 ms 12172 KB Output is correct
10 Correct 221 ms 12120 KB Output is correct
11 Correct 224 ms 13200 KB Output is correct
12 Correct 247 ms 13356 KB Output is correct
13 Correct 230 ms 13156 KB Output is correct
14 Correct 224 ms 13168 KB Output is correct
15 Correct 230 ms 11956 KB Output is correct
16 Correct 256 ms 11948 KB Output is correct
17 Correct 225 ms 12992 KB Output is correct
18 Correct 224 ms 13300 KB Output is correct
19 Correct 208 ms 11948 KB Output is correct
20 Correct 216 ms 12768 KB Output is correct
21 Correct 231 ms 12688 KB Output is correct
22 Correct 255 ms 12556 KB Output is correct
23 Correct 223 ms 11852 KB Output is correct
24 Correct 231 ms 12580 KB Output is correct
25 Correct 282 ms 17292 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 5648 KB Output is incorrect: {s, t} is wrong
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 5752 KB Output is incorrect: more than 100 calls to ask
2 Halted 0 ms 0 KB -