oj.uz

Submission #147512

# Submission time Handle Problem Language Result Execution time Memory
147512 2019-08-29T22:10:34 Z faremy Highway Tolls (IOI18_highway) C++14
40 / 100
 270 ms 17300 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 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])
			toogle(edge.id);

	long long shortestPath = ask(trafficCondition);
	for (int iNode = 0; iNode <= middle; iNode++)
		for (Edge &edge : graph[iNode])
			toogle(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;
				
				toogle(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++)
		toogle(parentEdge[candidates[iNode]]);

	long long shortestPath = ask(trafficCondition);
	for (int iNode = 0; iNode < (int)candidates.size() / 2; iNode++)
		toogle(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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4776 KB Output is correct
2 Correct 6 ms 4856 KB Output is correct
3 Correct 6 ms 4856 KB Output is correct
4 Correct 6 ms 4856 KB Output is correct
5 Correct 6 ms 4776 KB Output is correct
6 Correct 6 ms 4856 KB Output is correct
7 Runtime error 12 ms 9592 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4928 KB Output is correct
2 Correct 25 ms 5624 KB Output is correct
3 Correct 227 ms 12216 KB Output is correct
4 Correct 223 ms 12140 KB Output is correct
5 Correct 224 ms 12176 KB Output is correct
6 Correct 216 ms 12036 KB Output is correct
7 Correct 214 ms 12108 KB Output is correct
8 Correct 219 ms 12404 KB Output is correct
9 Correct 210 ms 12032 KB Output is correct
10 Correct 218 ms 12112 KB Output is correct
11 Correct 257 ms 12916 KB Output is correct
12 Correct 224 ms 13436 KB Output is correct
13 Correct 220 ms 13176 KB Output is correct
14 Correct 228 ms 13400 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 10664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4856 KB Output is correct
2 Correct 28 ms 5624 KB Output is correct
3 Correct 186 ms 10536 KB Output is correct
4 Correct 270 ms 12100 KB Output is correct
5 Correct 227 ms 12140 KB Output is correct
6 Correct 228 ms 12028 KB Output is correct
7 Correct 210 ms 11976 KB Output is correct
8 Correct 210 ms 11952 KB Output is correct
9 Correct 255 ms 12172 KB Output is correct
10 Correct 221 ms 12272 KB Output is correct
11 Correct 211 ms 13384 KB Output is correct
12 Correct 244 ms 13440 KB Output is correct
13 Correct 236 ms 13040 KB Output is correct
14 Correct 226 ms 13204 KB Output is correct
15 Correct 214 ms 11952 KB Output is correct
16 Correct 226 ms 12004 KB Output is correct
17 Correct 190 ms 13048 KB Output is correct
18 Correct 232 ms 13300 KB Output is correct
19 Correct 229 ms 11988 KB Output is correct
20 Correct 230 ms 12680 KB Output is correct
21 Correct 225 ms 12756 KB Output is correct
22 Correct 269 ms 12740 KB Output is correct
23 Correct 199 ms 11884 KB Output is correct
24 Correct 204 ms 12536 KB Output is correct
25 Correct 257 ms 17300 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 5672 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 36 ms 5736 KB Output is incorrect: more than 100 calls to ask
2 Halted 0 ms 0 KB -