Submission #560945

#	Time	Username	Problem	Language	Result	Execution time	Memory
560945		Yazan_Alattar	Torrent (COI16_torrent)	C++14	0 / 100	4 ms	1620 KiB

torrent

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 5007;
const ll inf = 1e9;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const double eps = 1e-6;
const int dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0};
const int block = 320;

vector <int> adj[M], va, vb;
int n, a, b;
bool ok;

int dfs(int node, int p, int wr){
    if(node == wr) return -inf;
    vector <int> v;

    for(auto i : adj[node]) if(i != p)
        v.pb(dfs(i, node, wr));

    sort(all(v), greater <int> ());
    if(!p){
        if(node == a) va = v;
        else vb = v;
    }

    int mx = 0;
    for(int i = 0; i < v.size(); ++i) mx = max(mx, v[i] + i);
    return mx + 1;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> a >> b;
    for(int i = 1; i < n; ++i){
        int x, y;
        cin >> x >> y;
        adj[x].pb(y);
        adj[y].pb(x);

        if(x == a && y == b) ok = 1;
        if(x == b && y == a) ok = 1;
    }

    dfs(a, 0, b);
    dfs(b, 0, a);
    va.pop_back(); vb.pop_back();

    for(int i = (int) va.size() - 1; i >= 0; --i){
        va[i] += i;
        if(i + 1 < va.size()) va[i] = max(va[i], va[i + 1]);
    }
    for(int i = (int) vb.size() - 1; i >= 0; --i){
        vb[i] += i;
        if(i + 1 < vb.size()) vb[i] = max(vb[i], vb[i + 1]);
    }

    int mx = 0;
    if(va.size()) mx = max(mx, va[0]);
    if(vb.size()) mx = max(mx, vb[0]);

    if(ok || (va.size() && va.back() < mx) || (vb.size() && vb.back() < mx) || va.size() != vb.size()) cout << mx << endl;
    else cout << mx + 1 << endl;
    return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'int dfs(int, int, int)':
torrent.cpp:36:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i = 0; i < v.size(); ++i) mx = max(mx, v[i] + i);
      |                    ~~^~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:59:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         if(i + 1 < va.size()) va[i] = max(va[i], va[i + 1]);
      |            ~~~~~~^~~~~~~~~~~
torrent.cpp:63:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         if(i + 1 < vb.size()) vb[i] = max(vb[i], vb[i + 1]);
      |            ~~~~~~^~~~~~~~~~~

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