Submission #642955

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
642955	2022-09-21T00:05:14 Z	ymm	Torrent (COI16_torrent)	C++17	100 / 100	118 ms	37732 KB

torrent

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 300010;
vector<int> A[N];
vector<int> path;
bool vis[N];
vector<int> timv[N];
int tim[N];
int timp[N];
int X, Y;
int n;

bool dfs1(int v, int p)
{
	if (v == Y) {
		path.push_back(v);
		vis[v] = 1;
		return 1;
	}
	for (int u : A[v]) {
		if (u == p)
			continue;
		if (dfs1(u, v)) {
			path.push_back(v);
			vis[v] = 1;
			return 1;
		}
	}
	return 0;
}

int dfs2(int v)
{
	vis[v] = 1;
	for (int u : A[v]) {
		if (!vis[u])
			timv[v].push_back(dfs2(u));
	}
	sort(timv[v].begin(), timv[v].end(), greater());
	tim[v] = 0;
	Loop (i,0,timv[v].size())
		tim[v] = max<int>(tim[v], timv[v][i] + i + 1);
	Loop (i,0,timv[v].size())
		timv[v][i] += i;
	LoopR (i,1,timv[v].size())
		timv[v][i-1] = max(timv[v][i-1], timv[v][i]);
	Loop (i,0,timv[v].size())
		timv[v][i] -= i;
	return tim[v];
}

bool bin(int x)
{
	memset(timp, 0, sizeof(timp));
	int l = 0, r = path.size() - 1;
	int t = 0;
	for (; l <= r; ++t) {
		if (l < r) {
			int v = path[l];
			int &p = timp[v];
			if (p < timv[v].size()) {
				     if (timv[v][p] + t + 1 > x)
					return 0;
				else if (timv[v][p] + t + 1 == x)
					++p;
				else
					++l;
			} else {
				++l;
			}
		}
		{
			int v = path[r];
			int &p = timp[v];
			if (p < timv[v].size()) {
				     if (timv[v][p] + t + 1 > x)
					return 0;
				else if (timv[v][p] + t + 1 == x)
					++p;
				else
					--r;
			} else {
				--r;
			}
		}
	}
	return 1;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> X >> Y;
	Loop (i,1,n) {
		int v, u;
		cin >> v >> u;
		A[v].push_back(u);
		A[u].push_back(v);
	}
	dfs1(X, -1);
	assert(path.size() >= 2);
	for (int u : path)
		dfs2(u);
	int l = (path.size()+1)/2 - 1;
	int r = N;
	while (l < r) {
		int m = (l + r)/2;
		if (bin(m))
			r = m;
		else
			l = m+1;
	}
	cout << l << '\n';
}

Compilation message

torrent.cpp: In function 'int dfs2(int)':
torrent.cpp:2:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
torrent.cpp:47:2: note: in expansion of macro 'Loop'
   47 |  Loop (i,0,timv[v].size())
      |  ^~~~
torrent.cpp:2:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
torrent.cpp:49:2: note: in expansion of macro 'Loop'
   49 |  Loop (i,0,timv[v].size())
      |  ^~~~
torrent.cpp:2:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
torrent.cpp:53:2: note: in expansion of macro 'Loop'
   53 |  Loop (i,0,timv[v].size())
      |  ^~~~
torrent.cpp: In function 'bool bin(int)':
torrent.cpp:67:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |    if (p < timv[v].size()) {
      |        ~~^~~~~~~~~~~~~~~~
torrent.cpp:81:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |    if (p < timv[v].size()) {
      |        ~~^~~~~~~~~~~~~~~~

Subtask #1

31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	15572 KB	Output is correct
2	Correct	9 ms	15572 KB	Output is correct
3	Correct	10 ms	15572 KB	Output is correct

Subtask #2

69.0 / 69.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	118 ms	36048 KB	Output is correct
2	Correct	116 ms	36604 KB	Output is correct
3	Correct	112 ms	36776 KB	Output is correct
4	Correct	108 ms	37732 KB	Output is correct
5	Correct	115 ms	36288 KB	Output is correct
6	Correct	111 ms	36284 KB	Output is correct
7	Correct	104 ms	37588 KB	Output is correct