oj.uz

Submission #147514

# Submission time Handle Problem Language Result Execution time Memory
147514 2019-08-29T22:26:22 Z faremy Highway Tolls (IOI18_highway) C++14
100 / 100
 387 ms 17956 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 toogledepth2(int node, int depth, int maxDepth)
{
	for (Edge &edge : tree[node])
	{
		if (depth >= maxDepth)
			toogle(edge.id);
		toogledepth2(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);
	toogledepth2(root, 0, edgesOnPath / 2);
	long long newShort = ask(trafficCondition);

	if (newShort == shortestPath)
	{
		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
	{
		toogledepth2(root, 0, edgesOnPath / 2);
		long long Tdepth = edgesOnPath / 2LL + (newShort - shortestPath) / (long long)(B - A);
		toogledepth2(root, 0, Tdepth);
		
		std::vector<int> nodes;
		makedepthset(root, nodes, 0, Tdepth);
		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];
		}

		toogledepth2(root, 0, Tdepth);
		toogledepth2(root, 0, edgesOnPath - Tdepth);

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

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4904 KB Output is correct
2 Correct 29 ms 5628 KB Output is correct
3 Correct 248 ms 12192 KB Output is correct
4 Correct 228 ms 12192 KB Output is correct
5 Correct 236 ms 12304 KB Output is correct
6 Correct 266 ms 12124 KB Output is correct
7 Correct 223 ms 12160 KB Output is correct
8 Correct 231 ms 12236 KB Output is correct
9 Correct 243 ms 12112 KB Output is correct
10 Correct 235 ms 12224 KB Output is correct
11 Correct 297 ms 14028 KB Output is correct
12 Correct 226 ms 14640 KB Output is correct
13 Correct 241 ms 14228 KB Output is correct
14 Correct 253 ms 13596 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6264 KB Output is correct
2 Correct 45 ms 7636 KB Output is correct
3 Correct 70 ms 9028 KB Output is correct
4 Correct 180 ms 16172 KB Output is correct
5 Correct 187 ms 16116 KB Output is correct
6 Correct 186 ms 17076 KB Output is correct
7 Correct 233 ms 17956 KB Output is correct
8 Correct 190 ms 16624 KB Output is correct
9 Correct 198 ms 16860 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4844 KB Output is correct
2 Correct 28 ms 5672 KB Output is correct
3 Correct 165 ms 10500 KB Output is correct
4 Correct 281 ms 12172 KB Output is correct
5 Correct 228 ms 12080 KB Output is correct
6 Correct 234 ms 12124 KB Output is correct
7 Correct 229 ms 12132 KB Output is correct
8 Correct 256 ms 12068 KB Output is correct
9 Correct 246 ms 12232 KB Output is correct
10 Correct 239 ms 12196 KB Output is correct
11 Correct 246 ms 13576 KB Output is correct
12 Correct 232 ms 14212 KB Output is correct
13 Correct 252 ms 14072 KB Output is correct
14 Correct 245 ms 14468 KB Output is correct
15 Correct 223 ms 12208 KB Output is correct
16 Correct 205 ms 12156 KB Output is correct
17 Correct 249 ms 13684 KB Output is correct
18 Correct 242 ms 14488 KB Output is correct
19 Correct 220 ms 12076 KB Output is correct
20 Correct 212 ms 14896 KB Output is correct
21 Correct 235 ms 12704 KB Output is correct
22 Correct 248 ms 12604 KB Output is correct
23 Correct 213 ms 11868 KB Output is correct
24 Correct 229 ms 12500 KB Output is correct
25 Correct 223 ms 17368 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 5752 KB Output is correct
2 Correct 32 ms 5752 KB Output is correct
3 Correct 265 ms 12640 KB Output is correct
4 Correct 288 ms 12956 KB Output is correct
5 Correct 332 ms 13644 KB Output is correct
6 Correct 372 ms 13876 KB Output is correct
7 Correct 365 ms 13932 KB Output is correct
8 Correct 323 ms 13984 KB Output is correct
9 Correct 275 ms 10904 KB Output is correct
10 Correct 287 ms 11520 KB Output is correct
11 Correct 324 ms 12044 KB Output is correct
12 Correct 329 ms 13064 KB Output is correct
13 Correct 353 ms 13468 KB Output is correct
14 Correct 334 ms 13740 KB Output is correct
15 Correct 334 ms 13744 KB Output is correct
16 Correct 297 ms 11884 KB Output is correct
17 Correct 207 ms 12716 KB Output is correct
18 Correct 222 ms 12948 KB Output is correct
19 Correct 229 ms 12988 KB Output is correct
20 Correct 221 ms 13036 KB Output is correct
21 Correct 307 ms 14068 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5752 KB Output is correct
2 Correct 32 ms 5752 KB Output is correct
3 Correct 265 ms 12592 KB Output is correct
4 Correct 305 ms 12780 KB Output is correct
5 Correct 296 ms 13044 KB Output is correct
6 Correct 317 ms 13676 KB Output is correct
7 Correct 267 ms 12528 KB Output is correct
8 Correct 254 ms 12736 KB Output is correct
9 Correct 276 ms 12928 KB Output is correct
10 Correct 306 ms 13672 KB Output is correct
11 Correct 324 ms 13852 KB Output is correct
12 Correct 323 ms 13864 KB Output is correct
13 Correct 292 ms 11932 KB Output is correct
14 Correct 257 ms 11336 KB Output is correct
15 Correct 282 ms 11848 KB Output is correct
16 Correct 282 ms 11528 KB Output is correct
17 Correct 312 ms 12048 KB Output is correct
18 Correct 269 ms 11620 KB Output is correct
19 Correct 322 ms 12960 KB Output is correct
20 Correct 300 ms 13308 KB Output is correct
21 Correct 328 ms 13800 KB Output is correct
22 Correct 372 ms 13864 KB Output is correct
23 Correct 350 ms 13772 KB Output is correct
24 Correct 331 ms 13744 KB Output is correct
25 Correct 367 ms 13936 KB Output is correct
26 Correct 332 ms 13772 KB Output is correct
27 Correct 219 ms 12848 KB Output is correct
28 Correct 220 ms 12744 KB Output is correct
29 Correct 217 ms 13064 KB Output is correct
30 Correct 269 ms 12924 KB Output is correct
31 Correct 209 ms 13108 KB Output is correct
32 Correct 227 ms 12676 KB Output is correct
33 Correct 223 ms 13176 KB Output is correct
34 Correct 218 ms 12708 KB Output is correct
35 Correct 216 ms 12880 KB Output is correct
36 Correct 227 ms 12656 KB Output is correct
37 Correct 214 ms 13068 KB Output is correct
38 Correct 244 ms 12924 KB Output is correct
39 Correct 387 ms 14396 KB Output is correct
40 Correct 313 ms 14556 KB Output is correct
41 Correct 320 ms 14072 KB Output is correct
42 Correct 310 ms 13964 KB Output is correct