oj.uz

Submission #147162

# Submission time Handle Problem Language Result Execution time Memory
147162 2019-08-28T07:40:55 Z fran_1024 Torrent (COI16_torrent) C++14
100 / 100
 911 ms 26448 KB 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector <int> neigh[300000];
int lg = 19;

pair <int, int> block;

int time(int p, int c) {
	int max = 0;
	int x = 1;
	vector <int> tms;
	for(int i = 0; i < neigh[c].size(); i++) {
		pair <int, int> pa1 = {.first = neigh[c][i], .second = c};
		pair <int, int> pa2 = {.first = c, .second = neigh[c][i]};
		//cout << "blocked: " << block.first << "," << block.second << "\n";
		if(neigh[c][i] != p && block != pa1 && block != pa2) {
			//cout << "iz " << c << " idemo na " << pa1.first << "," << pa1.second << "\n";
			tms.push_back(time(c, neigh[c][i]));
		}
	}
	//cout << "Cvor " << c + 1 << ": ";
	sort(tms.begin(), tms.end());
	reverse(tms.begin(), tms.end());
	for(int i = 0; i < tms.size(); i++) {
		if(max < tms[i] + x) max = tms[i] + x;
	//	cout << tms[i] + x << ' ';
		x++;
	}
	//cout << '\n';
	return max;
}

int plen;
bool dfsdone = false;

void dfs(int p, int c, int r, int path[], int len) {

	path[len] = c;
	if(c == r) {
		dfsdone = true;
		plen = len + 1;
		return;
	}
	
	for(int i = 0; i < neigh[c].size(); i++) {
		if(neigh[c][i] != p) {
			dfs(c, neigh[c][i], r, path, len + 1);
			if(dfsdone) return;
		}
	}
}

void blockln(int a, int b) {
	block.first = a;
	block.second = b;
}

int main() {
	int n, a, b, path[100000];
	cin >> n >> a >> b;
	a--;
	b--;
	for(int i = 0; i < n - 1; i++) {
		int x, y;
		cin >> x >> y;
		neigh[x - 1].push_back(y - 1);
		neigh[y - 1].push_back(x - 1);
	}
	
	/*cout << time(a, a);
	
	return 0;*/
	
	dfs(a, a, b, path, 0);
	
//	cout << "Path: ";
	//for(int i = 0; i < plen; i++) {
//		cout << path[i] << " ";
//	}
//	cout << "\n";
	
	int l = 0;
	int r = plen - 2;
	int sa, sb, mi;
	
	while(l < r) {
		mi = (l + r) / 2;
		blockln(path[mi], path[mi + 1]);
	//	cout << "Racunamo A\n";
		sa = time(a, a);
	//	cout << "Racunamo B\n";
		sb = time(b, b);
		if(sa > sb) r = mi;
		else l = mi + 1;
	}
	
	blockln(path[r], path[r + 1]);
	sa = time(a, a);
	
	int max1 = sa;
	
	if(r == 0) {
	//	cout << "jeeeej\n";
		cout << max1;
		return 0;
	}
	
	blockln(path[r], path[r - 1]);
	
	sb = time(b, b);
	
	int max2 = sb;
	
	if(max1 < max2) cout << max1;
	else cout << max2;
	
	return 0;
}

Compilation message

torrent.cpp: In function 'int time(int, int)':
torrent.cpp:15:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < neigh[c].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~
torrent.cpp:27:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < tms.size(); i++) {
                 ~~^~~~~~~~~~~~
torrent.cpp: In function 'void dfs(int, int, int, int*, int)':
torrent.cpp:48:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < neigh[c].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7416 KB Output is correct
2 Correct 10 ms 7416 KB Output is correct
3 Correct 10 ms 7544 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 821 ms 19144 KB Output is correct
2 Correct 831 ms 24392 KB Output is correct
3 Correct 758 ms 25928 KB Output is correct
4 Correct 818 ms 25012 KB Output is correct
5 Correct 911 ms 22728 KB Output is correct
6 Correct 780 ms 23444 KB Output is correct
7 Correct 788 ms 26448 KB Output is correct