제출 #147513

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
147513		faremy	통행료 (IOI18_highway)	C++14	51 / 100	285 ms	17292 KiB

highway

#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 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31