Submission #40070

#	Time	Username	Problem	Language	Result	Execution time	Memory
40070		KtlTheBest	Torrent (COI16_torrent)	C++14	0 / 100	107 ms	16812 KiB

torrent

/**
 	Template created by Danel Batyrbek
 	All rights are reserved 2018 (lol)
*/

#include <bits/stdc++.h>

#define speed_up ios_base :: sync_with_stdio(0);cin.tie(0)
#define fr first
#define sc second
#define mkp make_pair
#define pb push_back
#define eb emplace_back
#define ins insert
#define all(x) x.begin(), x.end()
#define debug(x) cerr << x << '\n';
#define YES "YES"
#define NO "NO"
#define skip continue
#define left(x) x << 1
#define rght(x) x << 1 | 1
#define forn(x, y, z) for(int x = y; x <= z; ++ x)
#define for1(x, y, z) for(int x = y; x >= z; -- x)
#define fname ""
using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef double ld;

const int N = 1e5 + 10;
const int mod = 1e9 + 7;
const int N3 = 1e3 + 10;
const int INF = 2e9 + 10;
const ll LINF = 2e18;

int n, a, b, cnt1[N], cnt2[N], dp[N], depth1[N], depth2[N], ans;
bool u[N];
vector <pair <pii, int> > v1[N], v2[N];
queue <pii> q;

void init(){
	forn(i, 1, n) u[i] = 0;
}

void dfs(int x, vector <pair <pii, int> > v[], int dep[], int arr[]){
	u[x] = 1;
	for(pair <pii, int> to : v[x]){
		if(!u[to.sc]){
			dep[to.sc] = dep[x] + 1;
			dfs(to.sc, v, dep, arr);
			arr[x] += arr[to.sc];
		}
	}
	for(pair <pii, int> to : v[x]){
		dep[x] = max(dep[x], dep[to.sc]);
	}
	arr[x] ++;
}

int main(){
#ifdef DEBUG
	freopen("in", "r", stdin);
#else	                    
	if(fname != ""){
	freopen(fname".in", "r", stdin);
	freopen(fname".out", "w", stdout);
	}
#endif
	cin >> n >> a >> b;
	forn(i, 1, n - 1){
		dp[i] = INF;
		int x, y;
		cin >> x >> y;
		v1[x].pb(mkp(mkp(0, 0), y));
		v1[y].pb(mkp(mkp(0, 0), x));
		v2[x].pb(mkp(mkp(0, 0), y));
		v2[y].pb(mkp(mkp(0, 0), x));
	}

	dp[n] = INF;

	dfs(a, v1, depth1, cnt1);
	init();
	dfs(b, v2, depth2, cnt2);

	forn(i, 1, n){
		for(pair <pii, int> x : v1[i]){
			x.fr.fr = -depth1[x.sc];
			x.fr.sc = -cnt1[x.sc];
		}
		for(pair <pii, int> x : v2[i]){
			x.fr.fr = -depth2[x.sc];
			x.fr.sc = -cnt2[x.sc];
		}
		sort(all(v1[i]));
		sort(all(v2[i]));
	}

	q.push(mkp(a, a));
	q.push(mkp(b, b));

	dp[a] = dp[b] = 0;

	while(q.size()){
		pii x = q.front();
		q.pop();
		int cnt = 1;
		if(x.sc == a){
			for(pair <pii, int> to : v1[x.fr]){
				if(dp[to.sc] > dp[x.fr] + cnt){
					dp[to.sc] = dp[x.fr] + cnt;
					cnt ++;
					q.push(mkp(to.sc, a));
				}
			}
		} else {
		    for(pair <pii, int> to : v2[x.fr]){
				if(dp[to.sc] > dp[x.fr] + cnt){
					dp[to.sc] = dp[x.fr] + cnt;
					cnt ++;
					q.push(mkp(to.sc, b));
				}
			}
		}
	}

	forn(i, 1, n) ans = max(ans, dp[i]);
	cout << ans;
	return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'int main()':
torrent.cpp:65:14: warning: comparison with string literal results in unspecified behaviour [-Waddress]
  if(fname != ""){
              ^
torrent.cpp:66:33: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen(fname".in", "r", stdin);
                                 ^
torrent.cpp:67:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen(fname".out", "w", stdout);
                                   ^

• Subtask 1: 0 / 31
• Subtask 2: 0 / 69