oj.uz

Submission #331183

# Submission time Handle Problem Language Result Execution time Memory
331183 2020-11-27T16:48:58 Z arujbansal Swapping Cities (APIO20_swap) C++17
0 / 100
 215 ms 39496 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 = 2e5 + 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;
    }
};

int n, m, fakeNode, timer = 0;
const int MAXK = 20;
vector<Edge> edges;
vi g[MAXN];
int par[MAXN], cost[MAXN], deg[MAXN], binlift[MAXN][MAXK], minCost[MAXN], tin[MAXN], tout[MAXN];
bool valid[MAXN];

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) {
    return (par[x] == x ? x : 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 = 2 * n, int p = -1) {
    if (valid[u]) minCost[u] = cost[u];

    if (p != -1) {
        binlift[u][0] = p;
        minCost[u] = min(minCost[u], minCost[p]);
    }

    tin[u] = timer++;

    for (int j = 1; j < MAXK; j++) {
        if (binlift[u][j - 1] < 0) continue;
        binlift[u][j] = binlift[binlift[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 y) {
    return (tin[x] <= tin[y] && tout[x] >= tout[y]);
}

int queryLCA(int u, int v) {
    if (isAnc(u, v)) return u;
    if (isAnc(v, u)) return v;

    for (int j = MAXK - 1; j >= 0; j--)
        if (binlift[u][j] > -1 && !isAnc(binlift[u][j], v))
            u = binlift[u][j];

    return binlift[u][0];
}

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 + 2 * n, 0);
    fakeNode = n;

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

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

    for (int i = 0; i <= 2 * n; i++) {
        for (int j = 0; j < MAXK; j++) {
            binlift[i][j] = -1;
        }
    }

    binlift[fakeNode][0] = -1;
    dfs();
}

int getMinimumFuelCapacity(int X, int Y) {
    int lca = queryLCA(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 5 ms 5868 KB Output is correct
2 Correct 4 ms 5868 KB Output is correct
3 Correct 4 ms 5868 KB Output is correct
4 Correct 5 ms 5996 KB Output is correct
5 Correct 5 ms 6124 KB Output is correct
6 Correct 5 ms 6124 KB Output is correct
7 Correct 5 ms 6272 KB Output is correct
8 Correct 7 ms 6124 KB Output is correct
9 Correct 92 ms 28896 KB Output is correct
10 Correct 114 ms 34016 KB Output is correct
11 Correct 120 ms 33524 KB Output is correct
12 Correct 131 ms 35168 KB Output is correct
13 Correct 101 ms 36724 KB Output is correct
14 Correct 94 ms 29152 KB Output is correct
15 Correct 183 ms 37100 KB Output is correct
16 Correct 180 ms 36752 KB Output is correct
17 Correct 215 ms 37880 KB Output is correct
18 Correct 160 ms 39496 KB Output is correct
19 Incorrect 69 ms 14508 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5868 KB Output is correct
2 Correct 4 ms 5868 KB Output is correct
3 Incorrect 161 ms 36740 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5868 KB Output is correct
2 Correct 5 ms 5868 KB Output is correct
3 Correct 4 ms 5868 KB Output is correct
4 Correct 4 ms 5868 KB Output is correct
5 Correct 5 ms 5996 KB Output is correct
6 Correct 5 ms 6124 KB Output is correct
7 Correct 5 ms 6124 KB Output is correct
8 Correct 5 ms 6272 KB Output is correct
9 Correct 7 ms 6124 KB Output is correct
10 Incorrect 5 ms 6124 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5868 KB Output is correct
2 Correct 5 ms 5868 KB Output is correct
3 Correct 4 ms 5868 KB Output is correct
4 Correct 4 ms 5868 KB Output is correct
5 Correct 5 ms 5996 KB Output is correct
6 Correct 5 ms 6124 KB Output is correct
7 Correct 5 ms 6124 KB Output is correct
8 Correct 5 ms 6272 KB Output is correct
9 Correct 7 ms 6124 KB Output is correct
10 Correct 92 ms 28896 KB Output is correct
11 Correct 114 ms 34016 KB Output is correct
12 Correct 120 ms 33524 KB Output is correct
13 Correct 131 ms 35168 KB Output is correct
14 Correct 101 ms 36724 KB Output is correct
15 Incorrect 5 ms 6124 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5868 KB Output is correct
2 Correct 4 ms 5868 KB Output is correct
3 Correct 4 ms 5868 KB Output is correct
4 Correct 5 ms 5996 KB Output is correct
5 Correct 5 ms 6124 KB Output is correct
6 Correct 5 ms 6124 KB Output is correct
7 Correct 5 ms 6272 KB Output is correct
8 Correct 7 ms 6124 KB Output is correct
9 Correct 92 ms 28896 KB Output is correct
10 Correct 114 ms 34016 KB Output is correct
11 Correct 120 ms 33524 KB Output is correct
12 Correct 131 ms 35168 KB Output is correct
13 Correct 101 ms 36724 KB Output is correct
14 Correct 94 ms 29152 KB Output is correct
15 Correct 183 ms 37100 KB Output is correct
16 Correct 180 ms 36752 KB Output is correct
17 Correct 215 ms 37880 KB Output is correct
18 Correct 160 ms 39496 KB Output is correct
19 Incorrect 161 ms 36740 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5868 KB Output is correct
2 Correct 5 ms 5868 KB Output is correct
3 Correct 4 ms 5868 KB Output is correct
4 Correct 4 ms 5868 KB Output is correct
5 Correct 5 ms 5996 KB Output is correct
6 Correct 5 ms 6124 KB Output is correct
7 Correct 5 ms 6124 KB Output is correct
8 Correct 5 ms 6272 KB Output is correct
9 Correct 7 ms 6124 KB Output is correct
10 Correct 92 ms 28896 KB Output is correct
11 Correct 114 ms 34016 KB Output is correct
12 Correct 120 ms 33524 KB Output is correct
13 Correct 131 ms 35168 KB Output is correct
14 Correct 101 ms 36724 KB Output is correct
15 Correct 94 ms 29152 KB Output is correct
16 Correct 183 ms 37100 KB Output is correct
17 Correct 180 ms 36752 KB Output is correct
18 Correct 215 ms 37880 KB Output is correct
19 Correct 160 ms 39496 KB Output is correct
20 Incorrect 161 ms 36740 KB Output isn't correct
21 Halted 0 ms 0 KB -