oj.uz

Submission #86173

# Submission time Handle Problem Language Result Execution time Memory
86173 2018-11-25T08:08:12 Z win11905 Torrent (COI16_torrent) C++11
100 / 100
 630 ms 25224 KB 
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author win11905
 */

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define long long long
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const long MOD = 1e9+7, LINF = 1e18 + 1e16;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

const int N = 3e5+5;

class torrent {
private:
	int n, a, b;
	int vl[N], par[N];
	vector<int> g[N];
	void dfs(int u, int p) {
		par[u] = p;
		for(int e : g[u]) if(e != p)
			dfs(vl[e] ^ u, e);
	}
	int dp[N], bad;
	void mic(int u, int p) {
		vector<int> ret;
		for(int e : g[u]) if(e != p && e != bad) {
			mic(vl[e] ^ u, e);
			ret.emplace_back(dp[vl[e] ^ u]);
		}
		sort(all(ret), greater<int>());
		for(int i = 0; i < ret.size(); ++i) dp[u] = max(dp[u], ret[i]+i+1);
	}
public:
	void solve(istream& cin, ostream& cout) {
		cin >> n >> a >> b;
		for(int i = 1, u, v; i < n; ++i) {
		    cin >> u >> v;
		    vl[i] = u ^ v;
		    g[u].emplace_back(i), g[v].emplace_back(i);
		}
		dfs(b, 0);
		vector<int> vec;
		int x = a;
		while(x != b) {
			vec.emplace_back(par[x]);
			x = vl[par[x]] ^ x;
		}
		int ans = 1e9;
		int l = 0, r = vec.size()-1;
		while(l <= r) {
			int m = l + r >> 1;
			memset(dp, 0, sizeof dp);
			bad = vec[m];
			mic(a, 0), mic(b, 0);
			ans = min(ans, max(dp[a], dp[b]));
			if(l == r) break;
			if(dp[a] < dp[b]) l = m+1;
			else if(dp[a] > dp[b]) r = m-1;
			else break;
		}
		cout << ans << endl;
	}
};

class Solver {
public:
	void solve(std::istream& in, std::ostream& out) {
		torrent *obj = new torrent();
		obj->solve(in, out);
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	Solver solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}

Compilation message

torrent.cpp: In member function 'void torrent::mic(int, int)':
torrent.cpp:39:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < ret.size(); ++i) dp[u] = max(dp[u], ret[i]+i+1);
                  ~~^~~~~~~~~~~~
torrent.cpp: In member function 'void torrent::solve(std::istream&, std::ostream&)':
torrent.cpp:59:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int m = l + r >> 1;
            ~~^~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 11000 KB Output is correct
2 Correct 15 ms 11132 KB Output is correct
3 Correct 14 ms 11132 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 630 ms 22572 KB Output is correct
2 Correct 563 ms 23812 KB Output is correct
3 Correct 483 ms 24844 KB Output is correct
4 Correct 547 ms 24844 KB Output is correct
5 Correct 557 ms 24844 KB Output is correct
6 Correct 567 ms 24844 KB Output is correct
7 Correct 478 ms 25224 KB Output is correct