oj.uz

Submission #331196

# Submission time Handle Problem Language Result Execution time Memory
331196 2020-11-27T17:01:49 Z arujbansal Swapping Cities (APIO20_swap) C++17
6 / 100
 384 ms 51144 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 + 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;

    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 11 ms 14060 KB Output is correct
2 Correct 10 ms 14060 KB Output is correct
3 Correct 10 ms 14060 KB Output is correct
4 Correct 10 ms 14188 KB Output is correct
5 Correct 12 ms 14316 KB Output is correct
6 Correct 12 ms 14316 KB Output is correct
7 Correct 11 ms 14316 KB Output is correct
8 Correct 11 ms 14316 KB Output is correct
9 Correct 155 ms 37216 KB Output is correct
10 Correct 199 ms 42592 KB Output is correct
11 Correct 201 ms 42080 KB Output is correct
12 Correct 211 ms 43616 KB Output is correct
13 Correct 175 ms 46048 KB Output is correct
14 Correct 190 ms 37344 KB Output is correct
15 Correct 283 ms 44524 KB Output is correct
16 Correct 293 ms 43792 KB Output is correct
17 Correct 304 ms 45384 KB Output is correct
18 Correct 358 ms 47688 KB Output is correct
19 Correct 103 ms 22316 KB Output is correct
20 Correct 293 ms 45920 KB Output is correct
21 Correct 289 ms 44828 KB Output is correct
22 Correct 343 ms 46792 KB Output is correct
23 Correct 381 ms 49224 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14060 KB Output is correct
2 Correct 10 ms 14060 KB Output is correct
3 Correct 354 ms 49568 KB Output is correct
4 Correct 384 ms 51144 KB Output is correct
5 Incorrect 378 ms 50168 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14060 KB Output is correct
2 Correct 11 ms 14060 KB Output is correct
3 Correct 10 ms 14060 KB Output is correct
4 Correct 10 ms 14060 KB Output is correct
5 Correct 10 ms 14188 KB Output is correct
6 Correct 12 ms 14316 KB Output is correct
7 Correct 12 ms 14316 KB Output is correct
8 Correct 11 ms 14316 KB Output is correct
9 Correct 11 ms 14316 KB Output is correct
10 Correct 155 ms 37216 KB Output is correct
11 Correct 199 ms 42592 KB Output is correct
12 Correct 201 ms 42080 KB Output is correct
13 Correct 211 ms 43616 KB Output is correct
14 Correct 175 ms 46048 KB Output is correct
15 Correct 11 ms 14316 KB Output is correct
16 Correct 13 ms 14316 KB Output is correct
17 Correct 11 ms 14316 KB Output is correct
18 Correct 11 ms 14316 KB Output is correct
19 Correct 11 ms 14316 KB Output is correct
20 Incorrect 11 ms 14316 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14060 KB Output is correct
2 Correct 10 ms 14060 KB Output is correct
3 Correct 10 ms 14060 KB Output is correct
4 Correct 10 ms 14188 KB Output is correct
5 Correct 12 ms 14316 KB Output is correct
6 Correct 12 ms 14316 KB Output is correct
7 Correct 11 ms 14316 KB Output is correct
8 Correct 11 ms 14316 KB Output is correct
9 Correct 155 ms 37216 KB Output is correct
10 Correct 199 ms 42592 KB Output is correct
11 Correct 201 ms 42080 KB Output is correct
12 Correct 211 ms 43616 KB Output is correct
13 Correct 175 ms 46048 KB Output is correct
14 Correct 190 ms 37344 KB Output is correct
15 Correct 283 ms 44524 KB Output is correct
16 Correct 293 ms 43792 KB Output is correct
17 Correct 304 ms 45384 KB Output is correct
18 Correct 358 ms 47688 KB Output is correct
19 Correct 354 ms 49568 KB Output is correct
20 Correct 384 ms 51144 KB Output is correct
21 Incorrect 378 ms 50168 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14060 KB Output is correct
2 Correct 11 ms 14060 KB Output is correct
3 Correct 10 ms 14060 KB Output is correct
4 Correct 10 ms 14060 KB Output is correct
5 Correct 10 ms 14188 KB Output is correct
6 Correct 12 ms 14316 KB Output is correct
7 Correct 12 ms 14316 KB Output is correct
8 Correct 11 ms 14316 KB Output is correct
9 Correct 11 ms 14316 KB Output is correct
10 Correct 155 ms 37216 KB Output is correct
11 Correct 199 ms 42592 KB Output is correct
12 Correct 201 ms 42080 KB Output is correct
13 Correct 211 ms 43616 KB Output is correct
14 Correct 175 ms 46048 KB Output is correct
15 Correct 190 ms 37344 KB Output is correct
16 Correct 283 ms 44524 KB Output is correct
17 Correct 293 ms 43792 KB Output is correct
18 Correct 304 ms 45384 KB Output is correct
19 Correct 358 ms 47688 KB Output is correct
20 Correct 354 ms 49568 KB Output is correct
21 Correct 384 ms 51144 KB Output is correct
22 Incorrect 378 ms 50168 KB Output isn't correct
23 Halted 0 ms 0 KB -