oj.uz

Submission #569581

# Submission time Handle Problem Language Result Execution time Memory
569581 2022-05-27T14:23:31 Z jcelin Torrent (COI16_torrent) C++14
100 / 100
 942 ms 66424 KB 
#include <bits/stdc++.h>
using namespace std;


typedef long long ll;
typedef long double ld;
typedef unsigned int ui;

#define ii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vii vector<ii>
#define vll vector<ll>
#define vpll vector<pll>
#define matrix vector<vi>
#define matrixLL vector<vLL>
#define vs vector<string>
#define vui vector<ui>
#define msi multiset<int>
#define mss multiset<string>
#define si set<int>
#define ss set<string>
#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int dxx[] = {-1, 1, 0, 0, 1, 1, -1, -1};
const int dyy[] = {0, 0, -1, 1, -1, 1, -1, 1};
const string abc="abcdefghijklmnopqrstuvwxyz";
const string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const ld pi = 3.14159265;
const int mod = 1e9 + 7;
const int MOD = 1e9 + 7;
const int MAXN = 1e6 + 7;
const int inf = mod;
const ll INF = 1e18;
const ll zero = ll(0);
const int logo = 20;
const int off = 1 << logo;
const int trsz = off << 1;

//fa-fb zabranjeni brid
int fa, fb, n, a, b;
vi g[MAXN];

int par[MAXN][logo], dep[MAXN];

vii edges;

int getLCA(int a, int b){
	if(dep[a] < dep[b]) swap(a, b);
	int delta = dep[a] - dep[b];
	for(int i=0; i<logo; i++) if(delta & (1 << i)) a = par[a][i];
	if(a == b) return a;
	for(int i=logo-1; i>=0; i--) if(par[a][i] != par[b][i]) a = par[a][i], b = par[b][i];
	return par[a][0];
}


void dfs(int u, int p = 1){
	par[u][0] = p;
	for(auto x: g[u]){
		if(x == p) continue;
		dep[x] = dep[u] + 1;
		dfs(x, u);	
	}
}

bool cmp(int a, int b){
	return a > b;
}


int solve(int u, int p = -1){
	vi tmp;
	for(auto x: g[u]){
		if(x == p) continue;
		if(u == fa and x == fb) continue;
		if(u == fb and x == fa) continue;
		tmp.PB(solve(x, u));
	}
	
	sort(all(tmp), cmp);
	int ret = 0;
	for(int i=0; i<tmp.size(); i++) ret = max(ret, tmp[i] + (i + 1));
	return ret;
}


int calc(){
	return max(solve(a), solve(b));
}

void solve(){
	cin >> n >> a >> b;
	for(int i=1, u, v; i < n; i++) cin >> u >> v, g[u].PB(v), g[v].PB(u);
	dfs(1);
	for(int i=1; i<=n; i++) for(int j=1; j<logo; j++) par[i][j] = par[par[i][j-1]][j-1];
	
	int c = getLCA(a, b);
	
	//int ans = inf;
	
	
	//pretvori u bin search
	int sa = a;
	while(sa != c){
		fa = sa;
		sa = par[sa][0];	
		fb = sa;
		//ans = min(ans, calc());
		edges.PB(MP(fa, fb));
	}
	
	
	vii tmp;
	//pretvroi u bin search
	int sb = b;
	while(sb != c){
		fa = sb;
		sb = par[sb][0];	
		fb = sb;
		//ans = min(ans, calc());
		tmp.PB(MP(fb, fa));
	}
	reverse(all(tmp));
	for(auto x: tmp) edges.PB(x);
	

	//for(auto x: edges) cout << x.X << " " << x.Y << "\n";
	
	int lo = 0, hi = edges.size() - 1;
	
	int ans = inf;
	while(lo <= hi){
		int mid = (lo + hi) / 2;
		fa = edges[mid].X, fb = edges[mid].Y;
		int vala = solve(a);
		int valb = solve(b);
		ans = min(ans, max(vala, valb));
		if(vala < valb) lo = mid + 1;
		else hi = mid - 1;;
	}
	
	lo = 0, hi = edges.size() - 1;
	while(lo <= hi){
		int mid = (lo + hi) / 2;
		fa = edges[mid].X, fb = edges[mid].Y;
		int vala = solve(a);
		int valb = solve(b);
		ans = min(ans, max(vala, valb));
		if(vala < valb) hi = mid - 1;
		else lo = mid + 1;
	}
	
	cout << ans << "\n";
} 


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t=1;
	//cin >> t;
	while(t--)solve();
	return 0;
}

Compilation message

torrent.cpp: In function 'int solve(int, int)':
torrent.cpp:94:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |  for(int i=0; i<tmp.size(); i++) ret = max(ret, tmp[i] + (i + 1));
      |               ~^~~~~~~~~~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23892 KB Output is correct
2 Correct 17 ms 23948 KB Output is correct
3 Correct 13 ms 23892 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 857 ms 60836 KB Output is correct
2 Correct 942 ms 63232 KB Output is correct
3 Correct 912 ms 65332 KB Output is correct
4 Correct 880 ms 64012 KB Output is correct
5 Correct 918 ms 61100 KB Output is correct
6 Correct 801 ms 61376 KB Output is correct
7 Correct 712 ms 66424 KB Output is correct