Submission #713023

#	Time	Username	Problem	Language	Result	Execution time	Memory
713023		stevancv	Torrent (COI16_torrent)	C++14	31 / 100	2082 ms	28512 KiB

torrent

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 3e5 + 2;
const int inf = 1e9;
vector<pair<int, int>> g[N];
int par[N];
void Dfs(int s, int e) {
    for (auto u : g[s]) {
        if (u.first == e) continue;
        par[u.first] = u.second;
        Dfs(u.first, s);
    }
}
int Dfs1(int s, int e, int c) {
    vector<int> all;
    for (auto u : g[s]) {
        if (u.first == e || u.second == c) continue;
        all.push_back(Dfs1(u.first, s, c));
    }
    sort(all.rbegin(), all.rend());
    int o = 0;
    for (int i = 0; i < all.size(); i++) {
        smax(o, all[i] + i + 1);
    }
    return o;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, a, b;
    cin >> n >> a >> b;
    vector<int> u(n - 1), v(n - 1);
    for (int i = 0; i < n - 1; i++) {
        cin >> u[i] >> v[i];
        g[u[i]].push_back({v[i], i});
        g[v[i]].push_back({u[i], i});
        par[i] = -1;
    }
    Dfs(a, 0);
    for (int i = 0; i < n - 1; i++) {
        if (par[v[i]] != i) swap(u[i], v[i]);
    }
    vector<int> p;
    int x = b;
    while (x != a) {
        p.push_back(par[x]);
        x = u[par[x]];
    }
    int sz = p.size();
    if (a == b) {
        cout << Dfs1(a, 0, -1) << en;
        return 0;
    }
    int ans = inf;
    for (int i : p) smin(ans, max(Dfs1(a, 0, i), Dfs1(b, 0, i)));
    cout << ans << en;
    return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'int Dfs1(int, int, int)':
torrent.cpp:28:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for (int i = 0; i < all.size(); i++) {
      |                     ~~^~~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:56:9: warning: unused variable 'sz' [-Wunused-variable]
   56 |     int sz = p.size();
      |         ^~

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