Submission #88631

#	Time	Username	Problem	Language	Result	Execution time	Memory
88631		Gogotchuri	Triumphal arch (POI13_luk)	C++14	100 / 100	1138 ms	38212 KiB

luk

#include <iostream>
#include <vector>

using namespace std;

#define MAX_NUM 300001
#define vi vector<int>
#define loop(n) for(int i = 0; i < (n); i++)
#define it_loop(cont) for(auto &elem : cont)

void read(vi * graph, int &n_nodes) {
	cin >> n_nodes;

	loop(n_nodes - 1) {
		int node1, node2;
		cin >> node1 >> node2;
		graph[node1].emplace_back(node2);
		graph[node2].emplace_back(node1);
	}

}

void depth_first(int cur, int prev, int &m, int *memo, vi * graph) {
	memo[cur] = m - (int)graph[cur].size();
	memo[cur] += (prev) ? 1 : 0;

	it_loop(graph[cur]) {
		if (elem == prev) continue;
		depth_first(elem, cur, m, memo, graph);
		if (memo[elem] < 0) memo[cur] += memo[elem];
	}
}

int b_search(int n_nodes, int &cur_node, int *memo, vi *graph) {
	int start_node = 0, end_node = n_nodes;

	while (start_node < end_node) {
		int m = (start_node + end_node) >> 1;
		cur_node = m;
		depth_first(1, 0, cur_node, memo, graph);
		memo[1] < 0 ? start_node = m + 1 : end_node = m;
	}

	return start_node;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n_nodes, cur_node, *memo;
	memo = new int[MAX_NUM];

	vi * graph = new vi[MAX_NUM];

	read(graph, n_nodes);
	cout << b_search(n_nodes, cur_node, memo, graph) << endl;
	
	delete[] memo;
	delete[] graph;

	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10