Submission #125676

#	Time	Username	Problem	Language	Result	Execution time	Memory
125676		srvlt	Shymbulak (IZhO14_shymbulak)	C++14	0 / 100	1545 ms	28476 KiB

shymbulak

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define int long long
using namespace std;

const int N = 2e5 + 3;
int n, parent[N], sz[N], d[2][N], deg[N], X, Y;
int up[18][N], tin[N], tout[N], timer, h[N], dist[N];
bool used[2][N], c[2][N];
vector <int> q[N];

void make_set(int x) {
    parent[x] = x;
    sz[x] = 1;
}

int find_set(int x) {
    if (x == parent[x])
        return x;
    return parent[x] = find_set(parent[x]);
}

void union_set(int x, int y) {
    x = find_set(x);
    y = find_set(y);
    if (x != y) {
        if (sz[x] < sz[y])
            swap(x, y);
        parent[y] = x;
        sz[x] += sz[y];
    }
}

void bfs(int t, int v) {
    queue <int> bq;
    used[t][v] = true;
    bq.push(v);
    while (!bq.empty()) {
        int z = bq.front();
        bq.pop();
        for (auto i : q[z]) {
            if (used[t][i])
                continue;
            c[t][i] = c[t][z];
            if ((z == X && i == Y) || (z == Y && i == X)) {
                c[t][i] = true;
            }
            used[t][i] = true;
            d[t][i] = d[t][z] + 1;
            bq.push(i);
        }
    }
}

bool upper(int v, int u) {
    return tin[v] <= tin[u] && tout[u] <= tout[v];
}

void dfs(int v, int p) {
    h[v] = h[p] + 1;
    tin[v] = ++timer;
    up[0][v] = p;
    for (int i = 1; i < 18; i++) {
        up[i][v] = up[i - 1][up[i - 1][v]];
    }
    for (auto i : q[v]) {
        if (i != p) {
            dfs(i, v);
        }
    }
    tout[v] = timer;
}

int lca(int v, int u) {
    if (upper(v, u)) {
        return v;
    }
    if (upper(u, v)) {
        return u;
    }
    for (int i = 17; i >= 0; i--) {
        if (!upper(up[i][v], u)) {
            v = up[i][v];
        }
    }
    return up[0][v];
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    for (int i = 1; i <= n; i++) {
        make_set(i);
    }
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin>>x>>y;
        if (find_set(x) == find_set(y)) {
            X = x, Y = y;
            continue;
        }
        q[x].pb(y);
        q[y].pb(x);
        union_set(x, y);
    }
    q[X].push_back(Y);
    swap(q[X].front(), q[X].back());
    q[Y].push_back(X);
    swap(q[Y].front(), q[Y].back());
    bfs(0, X);
    bfs(1, Y);
    for (int i = 0; i < q[X].size(); i++) {
        if (q[X][i] == Y) {
            q[X].erase(q[X].begin() + i);
            break;
        }
    }
    for (int i = 0; i < q[Y].size(); i++) {
        if (q[Y][i] == X) {
            q[Y].erase(q[Y].begin() + i);
            break;
        }
    }
    dfs(1, 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            int x = i, y = j, tmp = N, magic = 0;
            if (upper(X, x) && !upper(X, y)) {
                tmp = min(tmp, h[x] - h[X] + d[0][y]);
                magic = max(magic, (int)c[0][y]);
            }
            if (upper(X, y) && !upper(X, x)) {
                tmp = min(tmp, h[y] - h[X] + d[0][x]);
                magic = max(magic, (int)c[0][x]);
            }
            if (upper(Y, x) && !upper(Y, y)) {
                tmp = min(tmp, h[x] - h[Y] + d[1][y]);
                magic = max(magic, (int)c[1][y]);
            }
            if (upper(Y, y) && !upper(Y, x)) {
                tmp = min(tmp, h[y] - h[Y] + d[1][x]);
                magic = max(magic, (int)c[1][x]);
            }
            if (tmp != N) {
                if (tmp == h[x] + h[y] - 2 * h[lca(x, y)]) {
                    dist[tmp] += magic;
                }
            }   else {
                tmp = h[x] + h[y] - 2 * h[lca(x, y)];
            }
            dist[tmp]++;
        }
    }
    dist[1]++;
    for (int i = N - 1; i >= 0; i--) {
        if (dist[i] > 0) {
            return cout<<dist[i], 0;
        }
    }
}

Compilation message (stderr)

shymbulak.cpp: In function 'int main()':
shymbulak.cpp:120:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < q[X].size(); i++) {
                     ~~^~~~~~~~~~~~~
shymbulak.cpp:126:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < q[Y].size(); i++) {
                     ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50