Submission #531522

#	Time	Username	Problem	Language	Result	Execution time	Memory
531522		zlxFTH	Torrent (COI16_torrent)	C++11	100 / 100	316 ms	27352 KiB

torrent

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
 
const int maxn = 300005;
 
int n, a, b, t1, t2;
int head[maxn], to[maxn << 1], next[maxn << 1], lb, fa[maxn];
char mark[maxn];
std::vector<int> fson[maxn];
struct edge {
    int u, v;
} e[maxn];
int idx;
 
inline void ist(int aa, int ss) {
    to[lb] = ss;
    next[lb] = head[aa];
    head[aa] = lb;
    ++lb;
}
void dfs(int r, int p) {
    fa[r] = p;
    for (int j = head[r]; j != -1; j = next[j]) {
        if (to[j] != p) {
            dfs(to[j], r);
        }
    }
}
int get_ans(int r, int p, int mar) {
    fson[r].clear();
    int son_num = 0, mx = 0;
    for (int j = head[r]; j != -1; j = next[j]) {
        if (to[j] != p && mark[to[j]] != -mar) {
            fson[r].push_back(get_ans(to[j], r, mar));
            ++son_num;
        }
    }
    std::sort(fson[r].begin(), fson[r].end());
    for (std::vector<int>::iterator it = fson[r].begin(); it != fson[r].end(); ++it) {
        mx = std::max(mx, *it + son_num);
        --son_num;
    }
    return mx;
}
 
int main(void) {
    memset(head, -1, sizeof head);
    memset(next, -1, sizeof next);
    scanf("%d%d%d", &n, &a, &b);
    for (int i = 1; i < n; ++i) {
        scanf("%d%d", &t1, &t2);
        ist(t1, t2);
        ist(t2, t1);
    }
     
    dfs(a, 0);
    for (int i = b; i != a; i = fa[i]) {
        e[idx++] = (edge){fa[i], i};
    }
     
    int left = 0, right = idx - 1, mid;
    while (left < right) {
        mid = (left + right) >> 1;
        mark[e[mid].u] = -1;
        mark[e[mid].v] = 1;
        if (get_ans(a, 0, -1) > get_ans(b, 0, 1)) {
            left = mid + 1;
        }
        else {
            right = mid;
        }
        mark[e[mid].u] = mark[e[mid].v] = 0;
    }
    if (!left) {
        mark[e[0].u] = -1;
        mark[e[0].v] = 1;
        printf("%d\n", get_ans(b, 0, 1));
    }
    else {
        int ans1 = -666, ans2 = -666;
        mark[e[left].u] = -1;
        mark[e[left].v] = 1;
        ans1 = get_ans(b, 0, 1);
        mark[e[left].u] = mark[e[left].v] = 0;
         
        mark[e[left - 1].u] = -1;
        mark[e[left - 1].v] = 1;
        ans2 = get_ans(a, 0, -1);
        printf("%d\n", std::min(ans1, ans2));
    }
    return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'int main()':
torrent.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     scanf("%d%d%d", &n, &a, &b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         scanf("%d%d", &t1, &t2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~

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