Submission #571434

#	Time	Username	Problem	Language	Result	Execution time	Memory
571434		bojackduy	Torrent (COI16_torrent)	C++14	0 / 100	93 ms	36364 KiB

torrent

#include<iostream>
#include<queue>
#include<stack>
#include<algorithm>
#include<string.h>
#define task 
#define size() size() * 1ll 
#define all(x) (x).begin(), (x).end()
#define allr(x, sz) (x) + 1, (x) + 1 + sz
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define MASK(x) (1LL<<(x))
#define BIT(x,i) (((x)>>(i))&1)
#define numbit(x) __builtin_popcountll(x)

using namespace std;

const int N = 1e6 + 1;
const int M = 1e3 + 1;
const long long mod = 1e9 + 7;
const long long oo = 1e18 + 7;

typedef vector<int> vi;
typedef vector<pii> vii;
typedef long long ll;

template<class t>
bool mini(t &x,t y) {
    if (x > y) {
       x = y;
       return 1;
    }
return 0;
}
template<class t>
bool maxi(t &x,t y) {
    if (x < y) {
       x = y;
       return 1;
    }
return 0;
}
void file() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //freopen(task.in, r, stdin);
    //freopen(task.out, w, stdout);
return ;
}

int n, s, t;
int h[N], nxt[N];
vi a[N];
void dfs(int u, int chu) {
    h[u] = 1;
    for (auto v: a[u]) if (v != chu) {
        dfs(v, u);
        h[u] += h[v];
    }
}
void solve(int test = -1) {
    cin >> n >> s >> t;
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        a[x].pb(y);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i++) {
        sort(all(a[i]), [&](const int &x, const int &y) {
            return h[x] > h[y];
        });
        int k = a[i].size();
        for (int j = 0; j < k - 1; j++) {
            nxt[a[i][j]] = a[i][j + 1];

        }
    }
    queue<int> q;
    q.push(s);
    q.push(t);
    vi d(n + 1, -1);
    d[s] = 0;
    d[t] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (!u) continue;
        if (u != s && u != t) {
            int v = nxt[u];
            if (v == s || v == t) v = nxt[v];
            d[v] = d[u] + 1;
            q.push(v);
        }
        if (a[u].size() < 1) continue;
        int v = a[u][0];
        if (v == s || v == t) v = nxt[v];
        d[v] = d[u] + 1;
        q.push(v);
    }
    cout << *max_element(all(d)) - 1;
}

int32_t main()  {
    file();
    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; i++) {
        solve(i);
    }
return 0;
}

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