oj.uz

Submission #88631

# Submission time Handle Problem Language Result Execution time Memory
88631 2018-12-07T08:06:38 Z Gogotchuri Triumphal arch (POI13_luk) C++14
100 / 100
 1138 ms 38212 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7420 KB Output is correct
2 Correct 8 ms 7544 KB Output is correct
3 Correct 8 ms 7624 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7624 KB Output is correct
2 Correct 8 ms 7624 KB Output is correct
3 Correct 8 ms 7624 KB Output is correct
4 Correct 8 ms 7624 KB Output is correct
5 Correct 8 ms 7624 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7624 KB Output is correct
2 Correct 8 ms 7624 KB Output is correct
3 Correct 8 ms 7660 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7668 KB Output is correct
2 Correct 8 ms 7672 KB Output is correct
3 Correct 9 ms 7692 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8084 KB Output is correct
2 Correct 18 ms 8564 KB Output is correct
3 Correct 13 ms 8564 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 9424 KB Output is correct
2 Correct 40 ms 10932 KB Output is correct
3 Correct 28 ms 10932 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 12876 KB Output is correct
2 Correct 172 ms 16272 KB Output is correct
3 Correct 69 ms 16272 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 694 ms 18964 KB Output is correct
2 Correct 634 ms 27336 KB Output is correct
3 Correct 189 ms 27336 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1138 ms 27800 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1125 ms 27800 KB Output is correct
2 Correct 1102 ms 38212 KB Output is correct
3 Correct 534 ms 38212 KB Output is correct