Submission #846655

#	Time	Username	Problem	Language	Result	Execution time	Memory
846655		LaziChicken	Torrent (COI16_torrent)	C++17	0 / 100	361 ms	28464 KiB

torrent

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define eb emplace_back
#define task "Torrent"
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
#define fi first
#define se second
#define pii pair <int, int>
#define tii tuple <int, int, int>
using namespace std;
const int nmax = 300002;
int n, a, b, par[nmax];
vector <int> adj[nmax], Path;
int dp[nmax][2], ans = 1e9;
//0 a, 1 b
bool vs[nmax];
void get_path(int u)
{ 
    for (auto &v : adj[u])
    {
        if (v == par[u]) continue;
        par[v] = u;
        get_path(v);
    }
}
void solve(int u, int type)
{
    //dp[u][type] = 0;
    vector <int> best;
    for (auto &v : adj[u])
    {
        if (v == par[u] || vs[v]) continue;
        solve(v, type);
        best.eb(dp[v][type]);
    }
    sort(best.rbegin(), best.rend());
    for (int i = 0; i < best.size(); ++i)
        dp[u][type] = max(dp[u][type], best[i] + i + 1);
}
bool check(int u, int v)
{
    memset(dp, 0, sizeof dp);
    vs[v] = 1, solve(a, 0), vs[v] = 0;
    vs[u] = 1, solve(b, 1), vs[u] = 0;
    ans = min(ans, max(dp[a][0], dp[b][1]));
    return dp[a][0] < dp[b][1];
}
int main()
{
    if (ifstream(task".inp")) nx
    fast
    cin >> n >> a >> b;
    for (int u, v, i = 1; i < n; ++i)
    {
        cin >> u >> v;
        adj[u].eb(v);
        adj[v].eb(u);
    }
    get_path(a);
    int x = b;
    while(x != a)
    {
        Path.eb(x);
        x = par[x];
    }
    Path.eb(a);
    int l = 0, r = Path.size() - 2;
    while (l <= r)
    {
        int mid = l + r >> 1;
        if (check(Path[mid + 1], Path[mid]))
            l = mid + 1;
        else r = mid - 1;
    }
    cout << ans;
}

Compilation message (stderr)

torrent.cpp: In function 'void solve(int, int)':
torrent.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i = 0; i < best.size(); ++i)
      |                     ~~^~~~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:72:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |         int mid = l + r >> 1;
      |                   ~~^~~
torrent.cpp:7:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
      |            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:52:31: note: in expansion of macro 'nx'
   52 |     if (ifstream(task".inp")) nx
      |                               ^~
torrent.cpp:7:52: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
      |                                            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:52:31: note: in expansion of macro 'nx'
   52 |     if (ifstream(task".inp")) nx
      |                               ^~

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