oj.uz

Submission #331194

# Submission time Handle Problem Language Result Execution time Memory
331194 2020-11-27T17:01:02 Z arujbansal Swapping Cities (APIO20_swap) C++17
6 / 100
 436 ms 50760 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 = 5e5 + 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;
    }
};

int n, m, fakeNode, timer = 0;
const int MAXK = 21;
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 = fakeNode, 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);

    fakeNode--;

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

    for (int i = 0; i <= fakeNode; i++) {
        for (int j = 0; j < MAXK; j++) {
            binlift[i][j] = -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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12140 KB Output is correct
2 Correct 9 ms 12140 KB Output is correct
3 Correct 9 ms 12140 KB Output is correct
4 Correct 11 ms 12268 KB Output is correct
5 Correct 10 ms 12396 KB Output is correct
6 Correct 9 ms 12396 KB Output is correct
7 Correct 10 ms 12396 KB Output is correct
8 Correct 10 ms 12396 KB Output is correct
9 Correct 154 ms 36960 KB Output is correct
10 Correct 200 ms 42208 KB Output is correct
11 Correct 198 ms 41824 KB Output is correct
12 Correct 204 ms 43488 KB Output is correct
13 Correct 171 ms 45792 KB Output is correct
14 Correct 159 ms 36960 KB Output is correct
15 Correct 312 ms 45284 KB Output is correct
16 Correct 290 ms 44040 KB Output is correct
17 Correct 320 ms 46024 KB Output is correct
18 Correct 367 ms 48200 KB Output is correct
19 Correct 100 ms 21292 KB Output is correct
20 Correct 297 ms 45280 KB Output is correct
21 Correct 292 ms 44444 KB Output is correct
22 Correct 326 ms 45896 KB Output is correct
23 Correct 375 ms 48200 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12140 KB Output is correct
2 Correct 9 ms 12140 KB Output is correct
3 Correct 341 ms 49412 KB Output is correct
4 Correct 353 ms 50760 KB Output is correct
5 Incorrect 436 ms 49784 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12140 KB Output is correct
2 Correct 9 ms 12140 KB Output is correct
3 Correct 9 ms 12140 KB Output is correct
4 Correct 9 ms 12140 KB Output is correct
5 Correct 11 ms 12268 KB Output is correct
6 Correct 10 ms 12396 KB Output is correct
7 Correct 9 ms 12396 KB Output is correct
8 Correct 10 ms 12396 KB Output is correct
9 Correct 10 ms 12396 KB Output is correct
10 Correct 9 ms 12396 KB Output is correct
11 Correct 10 ms 12416 KB Output is correct
12 Correct 10 ms 12396 KB Output is correct
13 Correct 10 ms 12524 KB Output is correct
14 Correct 10 ms 12396 KB Output is correct
15 Incorrect 10 ms 12396 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12140 KB Output is correct
2 Correct 9 ms 12140 KB Output is correct
3 Correct 9 ms 12140 KB Output is correct
4 Correct 9 ms 12140 KB Output is correct
5 Correct 11 ms 12268 KB Output is correct
6 Correct 10 ms 12396 KB Output is correct
7 Correct 9 ms 12396 KB Output is correct
8 Correct 10 ms 12396 KB Output is correct
9 Correct 10 ms 12396 KB Output is correct
10 Correct 154 ms 36960 KB Output is correct
11 Correct 200 ms 42208 KB Output is correct
12 Correct 198 ms 41824 KB Output is correct
13 Correct 204 ms 43488 KB Output is correct
14 Correct 171 ms 45792 KB Output is correct
15 Correct 9 ms 12396 KB Output is correct
16 Correct 10 ms 12416 KB Output is correct
17 Correct 10 ms 12396 KB Output is correct
18 Correct 10 ms 12524 KB Output is correct
19 Correct 10 ms 12396 KB Output is correct
20 Incorrect 10 ms 12396 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12140 KB Output is correct
2 Correct 9 ms 12140 KB Output is correct
3 Correct 9 ms 12140 KB Output is correct
4 Correct 11 ms 12268 KB Output is correct
5 Correct 10 ms 12396 KB Output is correct
6 Correct 9 ms 12396 KB Output is correct
7 Correct 10 ms 12396 KB Output is correct
8 Correct 10 ms 12396 KB Output is correct
9 Correct 154 ms 36960 KB Output is correct
10 Correct 200 ms 42208 KB Output is correct
11 Correct 198 ms 41824 KB Output is correct
12 Correct 204 ms 43488 KB Output is correct
13 Correct 171 ms 45792 KB Output is correct
14 Correct 159 ms 36960 KB Output is correct
15 Correct 312 ms 45284 KB Output is correct
16 Correct 290 ms 44040 KB Output is correct
17 Correct 320 ms 46024 KB Output is correct
18 Correct 367 ms 48200 KB Output is correct
19 Correct 341 ms 49412 KB Output is correct
20 Correct 353 ms 50760 KB Output is correct
21 Incorrect 436 ms 49784 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12140 KB Output is correct
2 Correct 9 ms 12140 KB Output is correct
3 Correct 9 ms 12140 KB Output is correct
4 Correct 9 ms 12140 KB Output is correct
5 Correct 11 ms 12268 KB Output is correct
6 Correct 10 ms 12396 KB Output is correct
7 Correct 9 ms 12396 KB Output is correct
8 Correct 10 ms 12396 KB Output is correct
9 Correct 10 ms 12396 KB Output is correct
10 Correct 154 ms 36960 KB Output is correct
11 Correct 200 ms 42208 KB Output is correct
12 Correct 198 ms 41824 KB Output is correct
13 Correct 204 ms 43488 KB Output is correct
14 Correct 171 ms 45792 KB Output is correct
15 Correct 159 ms 36960 KB Output is correct
16 Correct 312 ms 45284 KB Output is correct
17 Correct 290 ms 44040 KB Output is correct
18 Correct 320 ms 46024 KB Output is correct
19 Correct 367 ms 48200 KB Output is correct
20 Correct 341 ms 49412 KB Output is correct
21 Correct 353 ms 50760 KB Output is correct
22 Incorrect 436 ms 49784 KB Output isn't correct
23 Halted 0 ms 0 KB -