Submission #148166

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
148166	2019-08-31T16:08:48 Z	emaborevkovic	Torrent (COI16_torrent)	C++14	100 / 100	193 ms	35248 KB

torrent

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

#define pb push_back
#define trace(x) cerr << #x << " " << x << endl

const int N = 3*1e5+11;
int n, a, b;
vector <int> ls[N];
int boje[N];
int nasao;
int d[N];
vector <int> tr[N];
int bio[N];

void dfs (int x, int p) {
	if (x == b) {
		nasao = 1;
		boje[x] = 1;
		return;
	}
	for (int i=0;i<ls[x].size();i++) {
		if (ls[x][i] == p) continue;
		dfs (ls[x][i], x);
		if (nasao) {
			boje[x] = 1;
			return;
		}
	}
}

int prekomp (int x, int p) {
	if (ls[x].size() == 1) return d[x] = 0;
	vector <int> v;
	for (int i=0;i<ls[x].size();i++) {
		if (ls[x][i] == p) continue;
		v.pb(prekomp(ls[x][i], x));
	}
	sort(v.begin(), v.end());
	int dod = v.size();
	int ret = 0;
	for (int i=0;i<v.size();i++) {
		ret = max(v[i]+dod, ret);
		dod--;
	}
	return d[x] = ret;
}

void func (int x, int kol) {
	int kad = tr[x].size();
	if (kol < 0) return;
	for (int i=tr[x].size()-1;i>=0;i--) {
		if (tr[x][i] > kol) return;
		if (tr[x][i] == kol) kad = i;
	}
	kad = tr[x].size()-kad;
	bio[x] = 1;
	for (int i=0;i<ls[x].size();i++) {
		if (boje[ls[x][i]] && !bio[ls[x][i]]) {
			func (ls[x][i], kol-kad-1);
			break;
		} 
	}
}

bool prov (int x) {
	memset (bio, 0, sizeof bio);
	func (a, x);
	func (b, x);
	for (int i=0;i<n;i++) {
		if (boje[i] && !bio[i]) return 0;
	}
	return 1;
}

int main() {
	cin >> n >> a >> b;
	a--; b--;
	for (int i=0;i<n-1;i++) {
		int a1, a2;
		scanf("%d%d", &a1, &a2);
		a1--; a2--;
		ls[a1].pb(a2);
		ls[a2].pb(a1);
	}
	dfs (a, a);
	for (int i=0;i<n;i++) {
		if (boje[i]) {
			for (int j=0;j<ls[i].size();j++) {
				if (boje[ls[i][j]]) continue;
				prekomp (ls[i][j], i);
				tr[i].pb(d[ls[i][j]]);
			}
			sort(tr[i].begin(), tr[i].end());
			int dod = tr[i].size();
			for (int j=0;j<tr[i].size();j++) {
				tr[i][j] += dod;
				dod--;
			}
		} 
	}
	int lo = 0;
	int hi = N;
	while (lo < hi) {
		int mid = (lo+hi)/2;
		if (prov(mid)) hi = mid;
		else lo = mid+1;
	}
	cout << lo;
	return 0;
}

Compilation message

torrent.cpp: In function 'void dfs(int, int)':
torrent.cpp:27:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<ls[x].size();i++) {
               ~^~~~~~~~~~~~~
torrent.cpp: In function 'int prekomp(int, int)':
torrent.cpp:40:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<ls[x].size();i++) {
               ~^~~~~~~~~~~~~
torrent.cpp:47:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<v.size();i++) {
               ~^~~~~~~~~
torrent.cpp: In function 'void func(int, int)':
torrent.cpp:63:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<ls[x].size();i++) {
               ~^~~~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:94:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j=0;j<ls[i].size();j++) {
                 ~^~~~~~~~~~~~~
torrent.cpp:101:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j=0;j<tr[i].size();j++) {
                 ~^~~~~~~~~~~~~
torrent.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a1, &a2);
   ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1

31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	15608 KB	Output is correct
2	Correct	18 ms	15608 KB	Output is correct
3	Correct	18 ms	15608 KB	Output is correct

Subtask #2

69.0 / 69.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	173 ms	33168 KB	Output is correct
2	Correct	176 ms	34384 KB	Output is correct
3	Correct	182 ms	34880 KB	Output is correct
4	Correct	181 ms	35248 KB	Output is correct
5	Correct	183 ms	32764 KB	Output is correct
6	Correct	193 ms	33012 KB	Output is correct
7	Correct	192 ms	35156 KB	Output is correct