Submission #147682

#	Time	Username	Problem	Language	Result	Execution time	Memory
147682		saral	Torrent (COI16_torrent)	C++14	100 / 100	834 ms	26744 KiB

torrent

#include <bits/stdc++.h>

using namespace std;
int n, a, b, x, y;
const int N = 300100;
vector<int> graf[N];
vector<pair<int, int> >put;
int t = 0;
int bio[N];
int val[N];
vector<int>pom;
int node1, node2;
pair<int, int> kol[N];

void nadi (int node, int par) {
    ///cout << node << " " << par << " -> " << t << endl;
    ///system("pause");
    if (node == b) {
        t = 1;
        put.push_back(make_pair(node, par));
        return;
    }

    for (int i = 0; i < graf[node].size(); i++) {
        if (t == 1) {
            put.push_back(make_pair(node, par));
            return;
        }
        if (graf[node][i] != par) nadi (graf[node][i], node);
    }
    if (t == 1) {
        put.push_back(make_pair(node, par));
        return;
    }
    return;
}

void dfs (int node, int par) {
    for (int i = 0; i < graf[node].size(); i++) {
        if (graf[node][i] != par) {
                if ((node == node1 && graf[node][i] == node2) || (node == node2 && graf[node][i] == node1)) {}
                else dfs (graf[node][i], node);
        }
    }
    pom.clear();
    for (int i = 0; i < graf[node].size(); i++) {
        if (graf[node][i] != par) {
                if ((node == node1 && graf[node][i] == node2) || (node == node2 && graf[node][i] == node1)) {}
                else pom.push_back(val[graf[node][i]]);
        }
    }
    if (pom.size()==0) val[node]=0;
    else {
        sort (pom.begin(), pom.end());
        int o=1, maxi=0;
        for (int i = pom.size()-1; i >= 0; i-=1) {
            if (pom[i]+o >= maxi) maxi=pom[i]+o;
            o++;
        }
        val[node]=maxi;
    }
    return;
}

bool solve (int pos) {
    memset(val, 0, sizeof(val));
    dfs (a, 0);
    dfs (b, 0);
    /*<<pos << " " << node1 << " " << node2 << endl;
    for (int i = 1; i <= n; i++) cout << i << " "<< val[i] << endl;
    system("pause");*/
    kol[pos].first = val[a];
    kol[pos].second = val[b];
    //cout << pos << " " << kol[pos].first << " " << kol[pos].second << endl;
    if (val[b] > val[a]) return true;
    else return false;
}



int main () {
    cin >> n >> a >> b;
    for (int i = 0; i < n-1; i++) {
        cin >> x >> y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }

    nadi(a, 0);
    for (int i = 0; i < put.size(); i++) {
        if ((put[i].first == 0) || (put[i].second == 0)) put.erase(put.begin()+i);
    }

    for (int i = 0; i < put.size(); i++) {
        //cout << put[i].first << " " << put[i].second << endl;
    }
   // cout << endl;
    int lo = 0, hi = put.size()-1, mid;
    bool k=0;
    while (lo != hi) {
        mid = (lo+hi)/2;
        node1 = put[mid].first, node2 = put[mid].second;
        k = solve (mid);
        if (k) {
            hi=mid;
        }
        else {
            lo=mid+1;
        }
    }
    /*cout << lo << endl;
    cout << kol[lo].first << " " << kol[lo].second << endl;
    cout << kol[lo-1].first << " " << kol[lo].second << endl;*/
    node1 = put[lo].first, node2 = put[lo].second;
    solve (lo);
    if (lo != 0) {
            node1 = put[lo-1].first, node2 = put[lo-1].second;
            solve (lo-1);
    }
    if (lo != 0) cout << min (max(kol[lo].first, kol[lo].second), max(kol[lo-1].first, kol[lo-1].second));
    else cout << max(kol[lo].first, kol[lo].second);



return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'void nadi(int, int)':
torrent.cpp:24:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < graf[node].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~~~
torrent.cpp: In function 'void dfs(int, int)':
torrent.cpp:39:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < graf[node].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~~~
torrent.cpp:46:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < graf[node].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:90:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < put.size(); i++) {
                     ~~^~~~~~~~~~~~
torrent.cpp:94:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < put.size(); i++) {
                     ~~^~~~~~~~~~~~

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