oj.uz

Submission #146186

# Submission time Handle Problem Language Result Execution time Memory
146186 2019-08-22T17:37:45 Z BartolM Torrent (COI16_torrent) C++17
100 / 100
 666 ms 27124 KB 
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <pii, int> ppi;
typedef pair <int, pii> pip;

const int INF=0x3f3f3f3f;
const int N=3e5+5;

int n, A, B;
vector <int> ls[N];
vector <int> v;
int bio[N], dp[N];

int cmp(int a, int b) {
	if (dp[a]==dp[b]) return a<b;
	return dp[a]>dp[b];
}

int rek(int node, int par, int ne) {
	if (dp[node]!=-1) return dp[node];
	dp[node]=0;
	for (int sus:ls[node]) {
		if (sus==ne || sus==par) continue;
		rek(sus, node, ne);
	}
	sort(ls[node].begin(), ls[node].end(), cmp);
	int cnt=1;
	for (int sus:ls[node]) {
		if (sus==ne || sus==par) continue;
		dp[node]=max(dp[node], dp[sus]+cnt);
		cnt++;
	}
	return dp[node];
}

int dfs(int node) {
	if (node==A) return 1;
	if (bio[node]) return 0;
	bio[node]=1;
	int res=0;
	for (int sus:ls[node]) {
		res|=dfs(sus);
	}
	if (res) v.pb(node);
	return res;
}

void load() {
	scanf("%d %d %d", &n, &A, &B); A--; B--;
	for (int i=0; i<n-1; ++i) {
		int a, b;
		scanf("%d %d", &a, &b); a--; b--;
		ls[a].pb(b);
		ls[b].pb(a);
	}
}

void solve() {
	dfs(B);
	v.insert(v.begin(), A);
	/*printf("v: ");
	for (int x:v) printf("%d ", x);
	printf("\n");*/
	int lo=0, hi=v.size()-2, mid;
	while (lo<hi) {
		memset(dp, -1, sizeof dp);
		mid=(lo+hi)/2;
		int x=v[mid], y=v[mid+1];
		int fa=rek(A, -1, y), fb=rek(B, -1, x);
		if (fa>fb) hi=mid;
		else lo=mid+1;
	}
	//printf("lo == %d\n", lo);
	memset(dp, -1, sizeof dp);
	int x=v[lo], y=v[lo+1];
	int sol=rek(A, -1, y);
	memset(dp, -1, sizeof dp);
	if (lo!=0) sol=min(sol, rek(B, -1, v[lo-1]));
	printf("%d\n", sol);
}

int main() {
	load();
	solve();
	return 0;
}

Compilation message

torrent.cpp: In function 'void solve()':
torrent.cpp:88:6: warning: unused variable 'x' [-Wunused-variable]
  int x=v[lo], y=v[lo+1];
      ^
torrent.cpp: In function 'void load()':
torrent.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &A, &B); A--; B--;
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &a, &b); a--; b--;
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8568 KB Output is correct
2 Correct 10 ms 8568 KB Output is correct
3 Correct 11 ms 8668 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 615 ms 21484 KB Output is correct
2 Correct 666 ms 22648 KB Output is correct
3 Correct 558 ms 26996 KB Output is correct
4 Correct 518 ms 27068 KB Output is correct
5 Correct 659 ms 25428 KB Output is correct
6 Correct 476 ms 25132 KB Output is correct
7 Correct 458 ms 27124 KB Output is correct