Submission #696645

#	Time	Username	Problem	Language	Result	Execution time	Memory
696645		vjudge1	Torrent (COI16_torrent)	C++17	100 / 100	423 ms	28152 KiB

torrent

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
#define fir first
#define sec second
typedef vector <int> vi;
typedef vector <ll> vl;
template <typename __Tp> void read(__Tp &x) {
    int f = 0; x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = 1;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    if (f) x = -x;
}
template <typename __Tp1, typename ...__Tp2> void read(__Tp1 &x, __Tp2 &...y) { read(x), read(y...); }
template <typename __Tp> void write(__Tp x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + 48);
}
void write(char ch) { putchar(ch); }
template <typename __Tp1, typename ...__Tp2> void write(__Tp1 x, __Tp2 ...y) { write(x), write(y...); }

const int maxn = 3e5 + 10;
int n, s, t;
vi e[maxn];

int vis[maxn], a[maxn], tot;
int dfs(int u) {
    vis[u] = 1, a[++tot] = u;
    if (u == t) return 1;
    for (int v : e[u]) if (!vis[v] && dfs(v)) return 1;
    vis[u] = 0, --tot;
    return 0;
}

int f[maxn];
void dfs2(int u) {
    vis[u] = 1; vi vec;
    for (int v : e[u]) if (!vis[v]) dfs2(v), vec.push_back(f[v]);
    sort(begin(vec), end(vec), greater <int> ());
    f[u] = 0;
    for (int i = 1; i <= (int) vec.size(); ++i) f[u] = max(f[u], vec[i - 1] + i);
}
pii query(int x) {
    fill(vis, vis + n + 1, 0);
    vis[a[x + 1]] = 1, dfs2(s);
    vis[a[x + 1]] = 0, dfs2(t);
    return pii(f[s], f[t]);
}
int ask(int x) {
    if (x >= tot) return 1e9;
    pii p = query(x);
    return max(p.fir, p.sec);
}

int main() {
    read(n, s, t);
    for (int i = 1; i < n; ++i) {
        int u, v; read(u, v);
        e[u].push_back(v), e[v].push_back(u);
    }
    dfs(s);
    int l = 1, r = tot - 1, mid, res = 1;
    while (l <= r) {
        mid = (l + r) >> 1;
        pii p = query(mid);
        if (p.fir <= p.sec) res = mid, l = mid + 1;
        else r = mid - 1;
    }
    write(min(ask(res), ask(res + 1)), '\n');
    return 0;
}

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