Submission #40064

#	Time	Username	Problem	Language	Result	Execution time	Memory
40064		5ak0	Torrent (COI16_torrent)	C++14	0 / 100	1671 ms	21864 KiB

torrent

/*
ID: 5ak0
PROG:
LANG: C++11
*/

#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define mpr make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 7, MAXN = 3e5 + 10;

int a, b;
int n;
int x, y, res;
int d[MAXN], cnt[MAXN];
bool u[MAXN];
vector <int> g[MAXN];

int main(){
    cin >> n >> a >> b;
    for (int i = 1; i < n; ++i){
        cin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }
    queue <int> q;
    q.push(a);
    q.push(b);
    u[a] = 1;
    u[b] = 1;
    while (!q.empty()){
        int v = q.front();
        q.pop();
        ++cnt[v];
        int mx = -1, mxi = 0;
        for (auto to : g[v]){
            if (u[to] == 0){
                int cnt = 0;
                for (auto too : g[to])
                    cnt += (u[too] == 0);
                if (cnt > mx)
                    mx = cnt, mxi = to;
            }
        }
        if (mx != -1){
            q.push(v);
            q.push(mxi);
            u[mxi] = 1;
            d[mxi] = d[v] + cnt[v];
        }
    }
    for (int i = 1; i <= n; ++i)
    //    cerr << d[i] << " ";
        res = max(res, d[i]);
    cout << res;
    return 0;
}

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