Submission #249108

#	Time	Username	Problem	Language	Result	Execution time	Memory
249108		kingfran1907	Torrent (COI16_torrent)	C++14	100 / 100	693 ms	41584 KiB

torrent

#include <bits/stdc++.h>

using namespace std;
const int maxn = 3e5+10;

int n, a, b;
vector< pair<int, int> > graph[maxn];
bool bio[maxn];
vector<int> path;
vector<int> q;
int dp1[maxn], dp2[maxn];

void dfs(int pos) {
    bio[pos] = true;
    if (pos == b) copy(q.begin(), q.end(), back_inserter(path));
    else {
        for (int i = 0; i < graph[pos].size(); i++) {
            int tren = graph[pos][i].first;
            if (!bio[tren]) {
                q.push_back(graph[pos][i].second);
                dfs(tren);
                q.erase(q.end() - 1);
            }
        }
    }
}

int err;
vector<int> dj[maxn];
int f(int pos) {
    bio[pos] = true;
    dj[pos].clear();
    for (int i = 0; i < graph[pos].size(); i++) {
        int tren = graph[pos][i].first;
        int indx = graph[pos][i].second;
        if (!bio[tren] && indx != err) dj[pos].push_back(f(tren));
    }
    int sol = 0;
    sort(dj[pos].begin(), dj[pos].end());
    reverse(dj[pos].begin(), dj[pos].end());
    for (int i = 0; i < dj[pos].size(); i++)
        sol = max(sol, dj[pos][i] + i + 1);
    return sol;
}

int fa(int koj) {
    //printf("fa: %d\n", koj);
    if (dp1[koj] != -1) return dp1[koj];
    err = koj;
    memset(bio, false, sizeof bio);
    dp1[koj] = f(a);
    return dp1[koj];
}

int fb(int koj) {
    //printf("fb: %d\n", koj);
    if (dp2[koj] != -1) return dp2[koj];
    err = koj;
    memset(bio, false, sizeof bio);
    dp2[koj] = f(b);
    return dp2[koj];
}

inline int pred(int x) {
    return x / abs(x);
}

int main() {
    memset(bio, false, sizeof bio);
    memset(dp1, -1, sizeof dp1);
    memset(dp2, -1, sizeof dp2);

    scanf("%d%d%d", &n, &a, &b);
    for (int i = 1; i < n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        graph[x].push_back(make_pair(y, i));
        graph[y].push_back(make_pair(x, i));
    }
    dfs(a);

    int lo = 0, hi = path.size() - 1;
    while (lo < hi) {
        int mid = (lo + hi + 1) / 2;

        int ac = fa(path[mid]);
        int bc = fb(path[mid]);
        if (ac == bc) {
            printf("%d", ac);
            return 0;
        } else if (pred(ac - bc) != pred(fa(path[0]) - fb(path[0]))) hi = mid - 1;
        else lo = mid;
    }
    //printf("GOOD\n");

    int sol = max(fa(path[lo]), fb(path[lo]));
    lo = 0, hi = path.size() - 1;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        //printf("mid: %d\n", mid);

        int ac = fa(path[mid]);
        int bc = fb(path[mid]);
        if (ac == bc) {
            printf("%d", ac);
            return 0;
        } else if (pred(ac - bc) != pred(fa(path.back()) - fb(path.back()))) lo = mid + 1;
        else hi = mid;
    }
    printf("%d", min(sol, max(fa(path[lo]), fb(path[lo]))));
    return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'void dfs(int)':
torrent.cpp:17:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < graph[pos].size(); i++) {
                         ~~^~~~~~~~~~~~~~~~~~~
torrent.cpp: In function 'int f(int)':
torrent.cpp:33:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < graph[pos].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~~~
torrent.cpp:41:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < dj[pos].size(); i++)
                     ~~^~~~~~~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &a, &b);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~

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