Submission #983274

#	Time	Username	Problem	Language	Result	Execution time	Memory
983274		ZHIRDILBILDIZ	Swapping Cities (APIO20_swap)	C++14	6 / 100	557 ms	67392 KiB

swap

#include <bits/stdc++.h>
#include "swap.h"
#define fi first
#define se second
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>

using namespace std;
const int N = 3e5 + 10;
struct edge {
    int from, to, w;
    edge () {}
    edge (int a, int b, int c) {
        from = a,
            to = b,
                w = c;
    }
};
bool cmp (edge e1, edge e2) {
    return e1.w < e2.w;
}
vector<edge> roads;

int SZ;
int kol;
int p[N];
int sz[N];
int st[N];
int ed[N];
int dist[N];
bool cycle[N];
vector<pii> gr[N];

void init_dsu () {
    for (int i = 0; i < N; ++i)
        p[i] = i,
            st[i] = i,
                ed[i] = i;
}
int get (int u) {
    if (u != p[u])
        p[u] = get(p[u]);
    return p[u];
}
void join (int u, int v, int w) {
    // cout << "join " << u << ' ' << v << '\n';
    int u1 = u, v1 = v;
    u = get(u);
    v = get(v);
    if (u == v) {
        ++kol;
        // cout << "add_road " << kol << ' ' << u << ' ' << w << '\n';
        gr[kol].push_back({u, w});
        p[u] = kol;
        cycle[kol] = 1;
        return;
    }
    // cout << "segments, u, v " << u << ' ' << v << ' ' << st[u] << ' ' << ed[u] << ' ' << st[v] << ' ' << ed[v] << '\n';
    ++kol;
    cycle[kol] = (cycle[u] | cycle[v]);
    if ((u1 == st[u] || u1 == ed[u]) && (v1 == st[v] || v1 == ed[v])) {
        set<int> all;
        all.insert(st[u]);
        all.insert(ed[u]);
        all.insert(st[v]);
        all.insert(ed[v]);

        if (st[u] != ed[u])
            all.erase(u1);
        if (st[v] != ed[v])
            all.erase(v1);


        st[kol] = (*all.begin());
        ed[kol] = (*all.rbegin());
    } else {
        cycle[kol] = 1;
    }
    // cout << "add_road " << kol << ' ' << u << ' ' << v << ' ' << w << '\n';
    gr[kol].push_back({u, w});
    gr[kol].push_back({v, w});

    p[u] = kol;
    p[v] = kol;
}

int timer;
int tin[N];
int tout[N];
int lc[N][20];
int mx[N][20];

void dfs(int city, int pr, int ls) {
    // cout << "dfs("<<city<<")\n";
    tin[city] = ++timer;

    lc[city][0] = pr;
    mx[city][0] = ls;

    for (int i = 1; i < 20; ++i) {
        lc[city][i] = lc[lc[city][i - 1]][i - 1];
        mx[city][i] = max(mx[city][i - 1], mx[lc[city][i - 1]][i - 1]);
    }

    for (auto i : gr[city]) {
        dist[i.fi] = dist[city] + 1;
        dfs(i.fi, city, i.se);
    }
    tout[city] = ++timer;
}
bool upper(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}
int get_on_dist (int u, int x) {
    int abu = 0;
    for (int i = 19; i >= 0; --i)
        if (abu + (1 << i) < x && lc[u][i])
            u = lc[u][i];
    return u;
}
bool check_lca (int u, int v, int lca) {
    // cout << "check_lca u, v, lca = " << u << ' ' << v << ' ' << lca << ' ' << upper(lca, u) << ' ' << upper(lca, v) << '\n';
    if (upper(lca, u) && upper(lca, v))
        return 1;
    return 0;
}
int get_max (int lca, int v) {
    if (lca == v)
        return 0;
    int res = 0;
    for (int i = 19; i >= 0; --i)
        if (lc[v][i] && !upper(lc[v][i], lca)) {
            res = max(res, mx[v][i]);
            v = lc[v][i];
        }
    return max(res, mx[v][0]);
}

void init (int n, int m, vector<int> u, vector<int> v, vector<int> w) {

    kol = SZ = n;
    for (int i = 0; i < m; ++i) {
        u[i]++;
        v[i]++;
        edge e(u[i], v[i], w[i]);
        roads.push_back(e);
    }

    init_dsu();
    sort(roads.begin(), roads.end(), cmp);
    for (edge e : roads)
        join(e.from, e.to, e.w);
    // for (int i=1;i<=kol;++i) {
    //     cout<<cycle[i] << ' ';
    // }
    // cout << '\n';

    dfs(kol, 0, 0);

}
int getMinimumFuelCapacity (int u, int v) {
    if (u == v)
        return -1;
    ++u;
    ++v;

    int l = 0, r = kol;
    while (l + 1 < r) {
        int mid = (l + r) >> 1;
        int lca = get_on_dist(u, mid);
        // cout << "mid, lca = " << l << ' ' << r << ' ' << mid << ' ' << lca << ' ' << check_lca(u, v, lca) << ' ' << cycle[lca] << '\n';
        if (!check_lca(u, v, lca) || !cycle[lca]) {
            l = mid;
        } else {
            r = mid;
        }
    }
    if (r == kol)
        return -1;
    int lca = get_on_dist(u, r);
    // cout << "u, v, lca = " << u << ' ' << v << ' ' << lca << '\n';
    return max(get_max(lca, u), get_max(lca, v));
}

// signed main () {
//     // ios_base::sync_with_stdio(0);
//     // cin.tie(0), cout.tie(0);

//     int n, m, q;
//     cin >> n >> m;
//     vector<int> u(m), v(m), w(m);
//     for (int i = 0; i < m; ++i)
//         cin >> u[i] >> v[i] >> w[i];
//     init(n, m, u, v, w);

//     cin >> q;
//     while (q--) {
//         int x, y;
//         cin >> x >> y;
//         cout << getMinimumFuelCapacity(x, y) << '\n';
//     }

//     return 0;
// }
// 5 6
// 0 1 4
// 0 2 4
// 2 1 1
// 2 3 3
// 1 3 2
// 1 4 10
//---------------------------
// 10 9
// 0 1 1
// 0 2 1
// 1 3 1
// 2 4 1
// 4 5 1
// 5 6 1
// 6 7 1
// 7 8 1
// 8 9 1

• Subtask 1: 6 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27