oj.uz

Submission #40064

# Submission time Handle Problem Language Result Execution time Memory
40064 2018-01-26T09:36:41 Z 5ak0 Torrent (COI16_torrent) C++14
0 / 100
 1671 ms 21864 KB 
/*
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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 11688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 69.0

# Verdict Execution time Memory Grader output
1 Incorrect 1671 ms 21864 KB Output isn't correct
2 Halted 0 ms 0 KB -