oj.uz

Submission #331329

# Submission time Handle Problem Language Result Execution time Memory
331329 2020-11-28T03:05:15 Z arujbansal Swapping Cities (APIO20_swap) C++17
0 / 100
 485 ms 99520 KB 
#include "swap.h"
#include <bits/stdc++.h>

#define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define setIO(i, o) freopen(i, "r", stdin), freopen(o, "w", stdout)
#define rand_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int) (x).size()
#define lc(i) 2*i
#define rc(i) 2*i+1
//#define int long long
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vii = vector<ii>;
using vi = vector<int>;
using vvi = vector<vi>;
using vb = vector<bool>;
using vvb = vector<vb>;

//rand_init;

const int MAXN = 6e5 + 5, MAXM = 4e5 + 5, MOD = 1e9 + 7, INF = 1e9 + 5;

struct Edge {
    int u, v, w;

    Edge(int u, int v, int w) : u(u), v(v), w(w) {}

    bool operator<(const Edge &other) {
        return w < other.w;
    }
};

vi g[MAXN];

struct LCA {
    int n, k, timer;
    vector<int> tin, tout;
    vector<vector<int>> par;

    void init(int x) {
        n = x;
        k = 31 - __builtin_clz(n);
        timer = 0;
        tin.resize(n);
        tout.resize(n);
        par.assign(n + 1, vector<int>(k + 1, n));
    }

    void dfs(int u = 0, int p = -1) {
        tin[u] = timer++;
        par[u][0] = (p == -1 ? n : p);
        for (int j = 1; j <= k; j++) par[u][j] = par[par[u][j - 1]][j - 1];
        for (const auto &v : g[u]) if (v != p) dfs(v, u);
        tout[u] = timer - 1;
    }

    bool isAnc(int x, int v) {
        return tin[x] <= tin[v] && tout[x] >= tout[v];
    }

    int query(int u, int v) {
        if (isAnc(u, v)) return u;
        if (isAnc(v, u)) return v;
        for (int j = k; j >= 0; j--) if (!isAnc(par[u][j], v)) u = par[u][j];
        return par[u][0];
    }
};

int n, m, fakeNode, timer = 0;
const int MAXK = 22;
vector<Edge> edges;
int par[MAXN], cost[MAXN], deg[MAXN], minCost[MAXN];
bool valid[MAXN];
LCA binlift;

void addEdge(int u, int w) {
    g[u].pb(fakeNode);
    g[fakeNode].pb(u);

    cost[fakeNode] = w;
    valid[fakeNode] |= valid[u];
}

int get(int x) {
    if (par[x] == x) return x;
    return par[x] = get(par[x]);
}

void unite(int x, int y, int w) {
//    cout << "Edge unite: " << x << " " << y << " " << w << "\n";

    int u = get(x), v = get(y);

    deg[x]++;
    deg[y]++;

    valid[u] |= (deg[x] >= 3);
    valid[v] |= (deg[y] >= 3);

    u = get(u), v = get(v);

    if (u == v) {
        addEdge(u, w);
        par[u] = fakeNode;
        valid[fakeNode] = true;

        fakeNode++;
        return;
    }

    addEdge(u, w);
    addEdge(v, w);

    par[u] = fakeNode;
    par[v] = fakeNode;

    fakeNode++;
}

void dfs(int u = fakeNode, int p = -1) {

    if (valid[u]) minCost[u] = cost[u];

    if (p > -1)
        minCost[u] = min(minCost[u], minCost[p]);

//    cout << u << " " << minCost[u] << "\n";

    for (const auto &v : g[u])
        if (v != p)
            dfs(v, u);
}

void init(int N, int M, vi U, vi V, vi W) {
    n = N, m = M;

    for (int i = 0; i < m; i++)
        edges.eb(U[i], V[i], W[i]);

    sort(all(edges));

    // Initialise UFDS stuff
    iota(par, par + MAXN, 0);
    fakeNode = n;

    for (const auto &[u, v, w] : edges)
        unite(u, v, w);

    fakeNode--;

    for (int i = 0; i <= fakeNode; i++)
        minCost[i] = INF;

    binlift.init(fakeNode);
    binlift.dfs(fakeNode, -1);

    dfs();
}

int getMinimumFuelCapacity(int X, int Y) {
    int lca = binlift.query(X, Y);

//    cout << "LCA: " << lca << "\n";

    return (minCost[lca] < INF ? minCost[lca] : -1);
}

//void solve() {
//    int a, b;
//    cin >> a >> b;
//    vi u(b), v(b), wt(b);
//
//    for (int i = 0; i < b; i++)
//        cin >> u[i] >> v[i] >> wt[i];
//
//    init(a, b, u, v, wt);
//
//    int q;
//    cin >> q;
//    while (q--) {
//        int x, y;
//        cin >> x >> y;
//        cout << getMinimumFuelCapacity(x, y) << "\n";
//    }
//}
//
//signed main() {
//    FAST_IO;
//#ifdef arujbansal_local
//    setIO("input.txt", "output.txt");
//#endif
//
//    int tc = 1;
////    cin >> tc;
//    while (tc--) solve();
//}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16748 KB Output is correct
2 Correct 13 ms 16748 KB Output is correct
3 Correct 12 ms 16748 KB Output is correct
4 Runtime error 34 ms 34028 KB Execution killed with signal 6 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16748 KB Output is correct
2 Correct 13 ms 16748 KB Output is correct
3 Correct 412 ms 57476 KB Output is correct
4 Correct 422 ms 59400 KB Output is correct
5 Runtime error 485 ms 99520 KB Execution killed with signal 6 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 34 ms 33772 KB Execution killed with signal 6 (could be triggered by violating memory limits)

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 34 ms 33772 KB Execution killed with signal 6 (could be triggered by violating memory limits)

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16748 KB Output is correct
2 Correct 13 ms 16748 KB Output is correct
3 Correct 12 ms 16748 KB Output is correct
4 Runtime error 34 ms 34028 KB Execution killed with signal 6 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 34 ms 33772 KB Execution killed with signal 6 (could be triggered by violating memory limits)