#193894 (C++14) No.529 帰省ラッシュ

提出ソース

結果

問題	No.529 帰省ラッシュ
ユーザー	tansunogon
提出日時	2017-08-05 08:09:28
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	238 ms / 4,500 ms
コード長	15,104 bytes
コンパイル時間	2,008 ms
コンパイル使用メモリ	92,748 KB
実行使用メモリ	33,520 KB
最終ジャッジ日時	2024-05-09 16:52:18
合計ジャッジ時間	5,523 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	4 ms 5,376 KB
testcase_05	AC	4 ms 5,376 KB
testcase_06	AC	4 ms 5,376 KB
testcase_07	AC	4 ms 5,376 KB
testcase_08	AC	162 ms 18,624 KB
testcase_09	AC	155 ms 19,776 KB
testcase_10	AC	193 ms 26,484 KB
testcase_11	AC	198 ms 26,728 KB
testcase_12	AC	133 ms 17,152 KB
testcase_13	AC	155 ms 33,520 KB
testcase_14	AC	157 ms 22,016 KB
testcase_15	AC	238 ms 26,276 KB
testcase_16	AC	235 ms 26,280 KB
testcase_17	AC	192 ms 32,948 KB
testcase_18	AC	194 ms 32,880 KB
testcase_19	AC	192 ms 33,008 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

In member function 'void SegTree::update(int, int)',
    inlined from 'int Solver::query2(int, int)' at main.cpp:715:36:
main.cpp:51:71: warning: 'group_index_max' may be used uninitialized [-Wmaybe-uninitialized]
   51 |                         int value2 = data_[child_begin + (child_index ^ 1)];
      |                                                          ~~~~~~~~~~~~~^~~~
main.cpp: In member function 'int Solver::query2(int, int)':
main.cpp:650:21: note: 'group_index_max' was declared here
  650 |                 int group_index_max = -1;
      |                     ^~~~~~~~~~~~~~~

ソースコード

raw source code

#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>

class SegTree
{
public:
	// in the case where n = 5
	//
	// [------6------]
	// [--4--] [--5--]
	// [0] [1] [2] [3] [4]
	std::vector<int> data_;
	std::vector<int> index_;
	const int n_;

	SegTree(size_t n) : n_(n)
	{
		int data_size = 0;
		while (n > 0)
		{
			data_size += n;
			n /= 2;
		}
		data_ = std::vector<int>(data_size, -1);
		index_ = std::vector<int>(data_size);
		for (int i = 0; i < n_; ++i)
		{
			index_[i] = i;
		}
	}

	void update(int i, int value)
	{
		assert(i >= 0 && i < n_);

		data_[i] = value;
		int index = i;

		int child_begin = 0;
		int child_index = i;
		int parent_begin = n_;
		int parent_size = n_ / 2;
		int parent_index = i / 2;
		while (parent_index < parent_size)
		{
			int value2 = data_[child_begin + (child_index ^ 1)];
			if (value > value2)
			{
				data_[parent_begin + parent_index] = value;
				index_[parent_begin + parent_index] = index;
			}
			else
			{
				data_[parent_begin + parent_index]
					= value
					= value2;
				index_[parent_begin + parent_index]
					= index
					= index_[child_begin + (child_index ^ 1)];
			}

			child_begin = parent_begin;
			child_index = parent_index;
			parent_begin += parent_size;
			parent_size /= 2;
			parent_index /= 2;
		}
	}

	// max [0, i]
	int getmax(int i, int* index) const
	{
		assert(i >= 0 && i < n_);

		int ret_max = -1;
		int index_begin = 0;
		int size = n_;
		while (1)
		{
			if ((i & 1) == 0)
			{
				if (ret_max < data_[index_begin + i])
				{
					ret_max = data_[index_begin + i];
					*index = index_[index_begin + i];
				}
				if (i == 0)
				{
					return ret_max;
				}
				--i;
			}
			index_begin += size;
			size /= 2;
			i /= 2;
		}
	}

	// max [i, j]
	int getmax(int i, int j, int* index) const
	{
		assert(0 <= i && i <= j && j < n_);

		int ret_max = -1;
		int index_begin = 0;
		int size = n_;
		while (1)
		{
			if (i & 1)
			{
				if (ret_max < data_[index_begin + i])
				{
					ret_max = data_[index_begin + i];
					*index = index_[index_begin + i];
				}
				++i;
			}
			if ((j & 1) == 0)
			{
				if (ret_max < data_[index_begin + j])
				{
					ret_max = data_[index_begin + j];
					*index = index_[index_begin + j];
				}
				--j;
			}
			if (i > j)
			{
				return ret_max;
			}
			index_begin += size;
			size /= 2;
			i /= 2;
			j /= 2;
		}
	}
};

class Graph
{
private:
	std::vector<int> edge_data_;
	std::vector<int*> edge_;
	std::vector<int> length_;

public:
	// V : num of vertices
	// E : num of edges
	// Edge[i] = {A[i], B[i]}
	Graph(int V, int E, const int A[], const int B[])
	{
		edge_data_ = std::vector<int>(E * 2);
		edge_ = std::vector<int*>(V);
		length_ = std::vector<int>(V);

		for (int i = 0; i < E; ++i)
		{
			++length_[A[i]];
			++length_[B[i]];
		}

		edge_[0] = edge_data_.data();
		for (int i = 0; i < V - 1; ++i)
		{
			edge_[i + 1] = edge_[i] + length_[i];
		}

		memset(length_.data(), 0, V * sizeof(int));

		for (int i = 0; i < E; ++i)
		{
			edge_[A[i]][length_[A[i]]++] = B[i];
			edge_[B[i]][length_[B[i]]++] = A[i];
		}
	}

	// returns num of Vertices
	inline int getV() const
	{
		return length_.size();
	}

	// returns num of Edges
	inline int getE() const
	{
		return edge_data_.size() / 2;
	}

	inline int getLength(int nodeIndex) const
	{
		return length_[nodeIndex];
	}

	inline int getEdge(int nodeIndex, int index) const
	{
		return edge_[nodeIndex][index];
	}

	void print() const
	{
		for (int i = 0; i < getV(); ++i)
		{
			printf("%d : ", i);
			for (int j = 0; j < getLength(i); ++j)
			{
				printf("%d ", getEdge(i, j));
			}
			printf("\n");
		}
	}
};

class BiconnectGraph_
{
public:
	Graph* g_;
	std::vector<int>* index_;

	BiconnectGraph_(Graph* g)
	{
		Builder builder;
		*this = builder.DecomposeToBiconnectedComponents(g);
	}

protected:
	void close()
	{
		delete g_;
		delete index_;
	}

private:
	BiconnectGraph_(Graph* g, std::vector<int>* index)
		:g_(g),
		index_(index)
	{}

	class Builder
	{
	public:
		Graph* g;
		std::vector<int> ord;
		std::vector<int> low;
		std::vector<bool> visited;
		int k;

		std::vector<int> A;
		std::vector<int> B;
		std::vector<int>* newIndex;

		// 二重辺連結成分分解
		// use lowlink http://hos.ac/slides/20110504_graph.pdf
		BiconnectGraph_ DecomposeToBiconnectedComponents(Graph* g)
		{
			this->g = g;
			ord = std::vector<int>(g->getV());
			low = std::vector<int>(g->getV());
			visited = std::vector<bool>(g->getV());
			k = 0;

			A = std::vector<int>(g->getE());
			B = std::vector<int>(g->getE());
			newIndex = new std::vector<int>(g->getV());

			// update ord, low
			dfs_lowlink(0);

			// update k, A, B, newIndex
			visited.assign(g->getV(), false);
			k = 0;
			(*newIndex)[0] = 0;
			dfs_create_graph_info(0);

			//print();

			return BiconnectGraph_(
				new Graph(k + 1, k, A.data(), B.data()),
				newIndex);
		}

		// Lowlink
		// gain information (ord, low) for decomposition
		void dfs_lowlink(int u, int prev = -1)
		{
			visited[u] = true;
			low[u] = ord[u] = k;
			++k;
			for (int i = 0; i < g->getLength(u); ++i)
			{
				int v = g->getEdge(u, i);
				if (!visited[v])
				{
					dfs_lowlink(v, u);
					low[u] = std::min(low[u], low[v]);
				}
				else if (v != prev)
				{
					low[u] = std::min(low[u], ord[v]);
				}
			}
		}

		// create new graph info
		// change k, A, B, newIndex
		void dfs_create_graph_info(int u)
		{
			visited[u] = true;
			for (int i = 0; i < g->getLength(u); ++i)
			{
				int v = g->getEdge(u, i);
				if (!visited[v])
				{
					assert(ord[u] < ord[v]);
					if (ord[u] < low[v])
					{
						// (u, v) is a bridge
						A[k] = (*newIndex)[u];
						B[k] = (*newIndex)[v] = k + 1;
						k = k + 1;
					}
					else
					{
						(*newIndex)[v] = (*newIndex)[u];
					}
					dfs_create_graph_info(v);
				}
			}
		}

		void print() const
		{
			printf("| ord | low | visited | newIndex |\n");
			for (int i = 0; i < g->getV(); ++i)
			{
				printf("|%4d |%4d |     %3d | %8d |\n", ord[i],
				                                        low[i],
				                                        visited[i],
				                                        (*newIndex)[i]);
			}
		}
	};
};

class BiconnectGraph : private BiconnectGraph_
{
public:
	BiconnectGraph(Graph* g) : BiconnectGraph_(g) {}
	~BiconnectGraph()
	{
		close();
	}

	inline Graph& graph() const
	{
		return *g_;
	}

	inline std::vector<int>& index() const
	{
		return *index_;
	}

	void print() const
	{
		graph().print();

		printf("i: reindex\n");
		for (int i = 0; i < index().size(); ++i)
		{
			printf("%d : %d\n", i, index().at(i));
		}
	}
};


class HLDecompositionGraph
{
public:
	std::vector<int> index_to_groupid;
	std::vector<int> index_to_groupindex;
	std::vector<int> groupid_to_parent_groupid;
	std::vector<int> groupid_to_parent_groupindex;
	std::vector<int> groupid_to_size;
	int group_count;

	HLDecompositionGraph(BiconnectGraph* biGraph)
		: index_to_groupid(biGraph->index().size()),
		index_to_groupindex(biGraph->index().size()),
		groupid_to_parent_groupid(biGraph->graph().getV()),
		groupid_to_parent_groupindex(biGraph->graph().getV()),
		groupid_to_size(biGraph->graph().getV())
	{
		Builder builder;
		builder.HLDecompose(this, biGraph);
	}

	void print() const
	{
		printf(" i:   gid gindex\n");
		for (int i = 0; i < index_to_groupid.size(); ++i)
		{
			printf("%2d: %5d %5d\n",
				i,
				index_to_groupid[i],
				index_to_groupindex[i]);
		}

		printf("gid:   p_gid p_gindex\n");
		for (int i = 0; i < groupid_to_parent_groupid.size(); ++i)
		{
			printf("%2d: %5d %5d\n",
				i,
				groupid_to_parent_groupid[i],
				groupid_to_parent_groupindex[i]);
		}
	}

	class Builder
	{
	public:
		HLDecompositionGraph* decomposision;
		Graph* g;
		BiconnectGraph* bg;
		// last group id
		int k;
		std::vector<int> depth_;
		std::vector<int> pre_index_to_groupid;
		std::vector<int> pre_index_to_groupindex;
		
		void HLDecompose(HLDecompositionGraph* decomposition, BiconnectGraph* g)
		{
			this->decomposision = decomposition;
			this->g = &g->graph();
			bg = g;
			k = 0;
			depth_ = std::vector<int>(g->graph().getV());
			pre_index_to_groupid = std::vector<int>(g->graph().getV());
			pre_index_to_groupindex = std::vector<int>(g->graph().getV());

			// find deepest node (doesnt make much of difference)
			// use this (submission 193255) => 256 ms
			// not use  (submission 193256) => 256 ms
			NodeInfo deepest_node = dfs_find_deepest(0);

			// update depth_
			dfs_depth(deepest_node.index);

			// HL decomposition
			dfs_hl_decomposition(deepest_node.index, 0, 0);

			// pre_index to decomposition.index
			for (int i = 0; i < g->index().size(); ++i)
			{
				decomposision->index_to_groupid[i]
					= pre_index_to_groupid[g->index()[i]];
				decomposision->index_to_groupindex[i]
					= pre_index_to_groupindex[g->index()[i]];
			}
			decomposision->group_count = k + 1;
		}

		struct NodeInfo
		{
			int depth;
			int index;
		};

		NodeInfo dfs_find_deepest(int u, int prev = -1)
		{
			NodeInfo info = {0, u};
			for (int i = 0; i < g->getLength(u); ++i)
			{
				int v = g->getEdge(u, i);
				if (v != prev)
				{
					NodeInfo leafInfo = dfs_find_deepest(v, u);
					if (leafInfo.depth > info.depth)
					{
						info = leafInfo;
					}
				}
			}
			++info.depth;
			return info;
		}

		// update depth_
		int dfs_depth(int u, int prev = -1)
		{
			int depth = 0;
			for (int i = 0; i < g->getLength(u); ++i)
			{
				int v = g->getEdge(u, i);
				if (v != prev)
				{
					depth = std::max(depth, dfs_depth(v, u));
				}
			}
			depth_[u] = depth;
			return depth + 1;
		}

		void dfs_hl_decomposition(int u,
		                          int group_id,
		                          int group_index,
		                          int prev = -1)
		{
			pre_index_to_groupid[u] = group_id;
			pre_index_to_groupindex[u] = group_index;
			++decomposision->groupid_to_size[group_id];

			int max_depth = -1;
			int max_depth_index = -1;
			for (int i = 0; i < g->getLength(u); ++i)
			{
				int v = g->getEdge(u, i);
				if (v != prev)
				{
					if (depth_[v] > max_depth)
					{
						max_depth = depth_[v];
						max_depth_index = v;
					}
				}
			}

			for (int i = 0; i < g->getLength(u); ++i)
			{
				int v = g->getEdge(u, i);
				if (v != prev)
				{
					if (v == max_depth_index)
					{
						// Heavy
						dfs_hl_decomposition(v, group_id, group_index + 1, u);
					}
					else
					{
						// Light
						++k;
						decomposision->groupid_to_parent_groupid[k] = group_id;
						decomposision->groupid_to_parent_groupindex[k] = group_index;
						dfs_hl_decomposition(v, k, 0, u);
					}
				}
			}
		}
	};
};

class Solver
{
public:
	using QueType = std::priority_queue<int>;

	HLDecompositionGraph* g;
	std::vector<std::vector<QueType>>* que_list;
	std::vector<SegTree>* seg_list;


	// V : num of vertices
	// E : num of edges
	// Edge[i] = {A[i], B[i]}
	Solver(int V, int E, const int A[], const int B[], const int add_count[])
	{
		// initialize HLDecompositionGraph
		Graph original_graph(V, E, A, B);
		BiconnectGraph biconnect_graph(&original_graph);
		g = new HLDecompositionGraph(&biconnect_graph);

		//original_graph.print();
		//biconnect_graph.print();
		//g->print();

		// initialize seq_list
		seg_list = new std::vector<SegTree>();
		seg_list->reserve(g->group_count);
		for (int i = 0; i < g->group_count; ++i)
		{
			seg_list->emplace_back(g->groupid_to_size[i]);
		}

		// initialize que_list
		que_list = new std::vector<std::vector<QueType>>(g->group_count);
		for (int i = 0; i < g->group_count; ++i)
		{
			(*que_list)[i] = std::vector<QueType>();
			(*que_list)[i].reserve(g->groupid_to_size[i]);
		}

		// reserve que
		{
			// initialize composed_add_count
			std::vector<std::vector<int>> composed_add_count(g->group_count);
			for (int i = 0; i < g->group_count; ++i)
			{
				composed_add_count[i] = std::vector<int>(g->groupid_to_size[i]);
			}

			// count
			for (int i = 0; i < V; ++i)
			{
				int group_id = g->index_to_groupid[i];
				int group_index = g->index_to_groupindex[i];
				composed_add_count[group_id][group_index] += add_count[i];
			}

			// reserve que
			for (int i = 0; i < g->group_count; ++i)
			{
				for (int j = 0; j < g->groupid_to_size[i]; ++j)
				{
					std::vector<int> que_vec;
					que_vec.reserve(composed_add_count[i][j]);
					(*que_list)[i].push_back(QueType(std::less<int>(),
					                         std::move(que_vec)));
				}
			}
		}
	}

	void query1(int u, int w)
	{
		int group_id = g->index_to_groupid[u];
		int group_index = g->index_to_groupindex[u];

		(*que_list)[group_id][group_index].push(w);

		auto& seg = (*seg_list)[group_id];
		if (w > seg.data_[group_index])
		{
			seg.update(group_index, w);
		}
	}

	int query2(int s, int t)
	{
		int group_id_0 = g->index_to_groupid[s];
		int group_index_0 = g->index_to_groupindex[s];
		int group_id_1 = g->index_to_groupid[t];
		int group_index_1 = g->index_to_groupindex[t];

		int max_value = -1;
		int group_id_max = -1;
		int group_index_max = -1;

		while (1)
		{
			if (group_id_0 == group_id_1)
			{
				if (group_index_0 > group_index_1)
				{
					std::swap(group_index_0, group_index_1);
				}
				int index;
				int value = (*seg_list)[group_id_0]
				            .getmax(group_index_0, group_index_1, &index);
				if (value > max_value)
				{
					max_value = value;
					group_id_max = group_id_0;
					group_index_max = index;
				}
				break;
			}

			if (group_id_0 < group_id_1)
			{
				std::swap(group_id_0, group_id_1);
				std::swap(group_index_0, group_index_1);
			}
			assert(group_id_0 > group_id_1);
			{
				int index;
				int value = (*seg_list)[group_id_0]
				            .getmax(group_index_0, &index);
				if (value > max_value)
				{
					max_value = value;
					group_id_max = group_id_0;
					group_index_max = index;
				}
				group_index_0 = g->groupid_to_parent_groupindex[group_id_0];
				group_id_0 = g->groupid_to_parent_groupid[group_id_0];
			}
		}

		if (max_value > 0)
		{
			assert(group_id_max != -1);
			assert(group_index_max != -1);

			// update que
			auto& que = (*que_list)[group_id_max][group_index_max];
			assert(que.top() == max_value);
			que.pop();

			// get que value
			int value;
			if (que.empty())
			{
				value = -1;
			}
			else
			{
				value = que.top();
			}

			// update segtree
			(*seg_list)[group_id_max].update(group_index_max, value);
		}

		return max_value;
	}

	~Solver()
	{
		delete g;
		delete que_list;
		delete seg_list;
	}
};

int N, M, Q;
int A[200000], B[200000];
int q[200000], a[200000], b[200000];
int add_count[100000] = {};

int main()
{
	scanf("%d %d %d", &N, &M, &Q);
	for (int i = 0; i < M; ++i)
	{
		scanf("%d %d", &A[i], &B[i]);
		--A[i];
		--B[i];
	}
	for (int i = 0; i < Q; ++i)
	{
		scanf("%d %d %d", &q[i], &a[i], &b[i]);
		if (q[i] == 1)
		{
			--a[i];
			++add_count[a[i]];
		}
		else
		{
			--a[i];
			--b[i];
		}
	}

	Solver solver(N, M, A, B, add_count);

	for (int i = 0; i < Q; ++i)
	{
		if (q[i] == 1)
		{
			solver.query1(a[i], b[i]);
		}
		else
		{
			printf("%d\n", solver.query2(a[i], b[i]));
		}
	}
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード