oj.uz

Submission #40063

# Submission time Handle Problem Language Result Execution time Memory
40063 2018-01-26T09:23:41 Z krauch Torrent (COI16_torrent) C++14
31 / 100
 2000 ms 68568 KB 
/*
 _    _    _______   _    _
| |  / /  |  _____| | |  / /
| | / /   | |       | | / /
| |/ /    | |_____  | |/ /
| |\ \    |  _____| | |\ \
| | \ \   | |       | | \ \
| |  \ \  | |_____  | |  \ \
|_|   \_\ |_______| |_|   \_\

*/
#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef double ld;
typedef pair <int, int> PII;
typedef pair <ll, ll> PLL;
typedef pair < ll, int > PLI;


#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define right(x) x << 1 | 1
#define left(x) x << 1
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)
#define mkp make_pair
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define y1 kekekek

#define fname ""

const ll ool = 1e18 + 9;
const int oo = 1e9 + 9, base = 1e9 + 7;
const ld eps = 1e-7;
const int N = 2e6 + 6;

int n, A, B, ans = oo, d[N];
vector < int > g[N], path, vec;

bool dfs(int v, int par) {
    vec.eb(v);
    if (v == B) path = vec;
    bool res = 0;
    vector < int > tmp;
    for (auto to : g[v]) {
        if (to == par) continue;
        bool val = dfs(to, v);
        res |= val;
        if (!val) tmp.eb(d[to]);
    }
    sort(all(tmp));
    reverse(all(tmp));
    forn(i, 0, sz(tmp) - 1) {
        d[v] = max(d[v], tmp[i] + i + 1);
    }
    vec.pop_back();
    return (res | (v == B));
}

int main() {
	ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

	#ifdef krauch
        freopen("input.txt", "r", stdin);
    #else
        //freopen(fname".in", "r", stdin);
        //freopen(fname".out", "w", stdout);
    #endif

    cin >> n >> A >> B;
    forn(i, 1, n - 1) {
        int x, y;
        cin >> x >> y;
        g[x].eb(y);
        g[y].eb(x);
    }

    dfs(A, 0);

    forn(i, 0, sz(path) - 2) {
        int vala = 0;
        if (!i) {
            vala = d[A];
        }
        else {
            vala = d[path[i]];
            for1(j, i - 1, 0) {
                vector < int > tmp;
                for (auto to : g[path[j]]) {
                    if (to != (j ? path[j - 1] : 0) && to != path[j + 1]) tmp.eb(d[to]);
                }
                tmp.eb(vala);
                sort(all(tmp));
                reverse(all(tmp));
                vala = 0;
                forn(k, 0, sz(tmp) - 1) vala = max(vala, tmp[k] + k + 1);
            }
        }
        int valb = 0;
        if (i == sz(path) - 2) {
            valb = d[B];
        }
        else {
            forn(j, i + 1, sz(path) - 1) {
                vector < int > tmp;
                for (auto to : g[path[j]]) {
                    if (to != (j ? path[j - 1] : 0) && to != (j < sz(path) - 1 ? path[j + 1] : 0)) tmp.eb(d[to]);
                }
                if (j != i + 1) tmp.eb(valb);
                sort(all(tmp));
                reverse(all(tmp));
                valb = 0;
                forn(k, 0, sz(tmp) - 1) valb = max(valb, tmp[k] + k + 1);
            }
        }
        ans = min(ans, max(vala, valb));
    }

    cout << ans << "\n";

	return 0;
}

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 56872 KB Output is correct
2 Correct 20 ms 56872 KB Output is correct
3 Correct 13 ms 56872 KB Output is correct

Subtask #2
0 / 69.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 68568 KB Execution timed out
2 Halted 0 ms 0 KB -