Cod sursa(job #2709497)

Utilizator ArdeleanOficialAlexandru ArdeleanOficial Data 20 februarie 2021 12:42:43
Problema Revolta Scor 0
Compilator cpp-64 Status done
Runda Arhiva ICPC Marime 2.38 kb
#include <bits/stdc++.h>

using namespace std;

//#define DEBUG

const int N = 1e5 + 7, INF = 1e9 + 7;

int dist[N], q[N], t[N];
vector < int > adia[N];
vector < int > edges;

bitset < N > locked;

int n;

pair < int, int > bfs(int nod, bool mod = 1) {
    fill(dist, dist + n, INF);
    dist[nod] = 0;
    if (mod)
        t[nod] = -1;
    int st(0), dr(-1), D(0), last(nod);
    q[++dr] = nod;
    while (st <= dr) {
        int x = q[st++];
        D = dist[x];
        last = x;
        for (int i : adia[x]) {
            if (locked[i])
                continue;
            int y = edges[i] ^ x;
            if (dist[y] == INF) {
                dist[y] = dist[x] + 1, q[++dr] = y;
                if (mod)
                    t[y] = i;
            }
        }
    }
    return {last, D};
}

int calc_diam(int A, vector < int > &diam) {
//    if (adia[A].size() > 1) {
//        cout << "Esti bou\n";
//        exit(0);
//    }
    diam.clear();
    int B = bfs(A).first;
    int l(0), cur(0);
    for (int i = B; i != A; i = edges[t[i]] ^ i) {
        locked[t[i]] = 1;
        cur = max(cur, bfs(i, 0).second + l);
        diam.push_back(cur);
        l++;
    }
    diam.push_back(l);
    for (int i = B; i != A; i = edges[t[i]] ^ i)
        locked[t[i]] = 0;
    return B;
}

int main()
{
    ifstream fin("revolta.in");
    ofstream fout("revolta.out");
    int t;
    fin >> t;
    while (t--) {
        int a, b;
        fin >> n;
        edges.clear();
        for (int i = 0; i < n; ++i)
            adia[i].clear();
        for (int i = 1; i < n; ++i) {
            fin >> a >> b;
            adia[a].push_back(edges.size());
            adia[b].push_back(edges.size());
            edges.push_back(a ^ b);
        }
        int A = bfs(0).first;
        vector < int > diam1, diam2;
        calc_diam(calc_diam(A, diam1), diam2);
        reverse(diam1.begin(), diam1.end());
        #ifdef DEBUG
        for (int i : diam1)
            fout << i << ' ';
        fout << '\n';
        for (int i : diam2)
            fout << i << ' ';
        fout << '\n';
        #endif // DEBUG
        int ans(diam1.front());
        for (int i = 1; i < diam1.size(); ++i)
            ans = min(ans, max(max(diam2[i - 1], diam1[i]), (diam2[i - 1] + 1) / 2 + (diam1[i] + 1) / 2 + 1));
        fout << ans << '\n';
    }
    return 0;
}