oj.uz

Submission #331193

# Submission time Handle Problem Language Result Execution time Memory
331193 2020-11-27T16:59:31 Z arujbansal Swapping Cities (APIO20_swap) C++17
6 / 100
 375 ms 49224 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 = 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 = 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 8 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 12268 KB Output is correct
5 Correct 9 ms 12396 KB Output is correct
6 Correct 9 ms 12396 KB Output is correct
7 Correct 10 ms 12544 KB Output is correct
8 Correct 10 ms 12396 KB Output is correct
9 Correct 153 ms 35316 KB Output is correct
10 Correct 201 ms 40544 KB Output is correct
11 Correct 198 ms 40160 KB Output is correct
12 Correct 209 ms 41652 KB Output is correct
13 Correct 186 ms 44000 KB Output is correct
14 Correct 165 ms 35424 KB Output is correct
15 Correct 298 ms 42476 KB Output is correct
16 Correct 283 ms 41872 KB Output is correct
17 Correct 307 ms 43464 KB Output is correct
18 Correct 365 ms 45768 KB Output is correct
19 Correct 102 ms 20268 KB Output is correct
20 Correct 291 ms 43744 KB Output is correct
21 Correct 286 ms 42908 KB Output is correct
22 Correct 303 ms 44872 KB Output is correct
23 Correct 371 ms 47176 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12140 KB Output is correct
2 Correct 9 ms 12140 KB Output is correct
3 Correct 375 ms 47512 KB Output is correct
4 Correct 345 ms 49224 KB Output is correct
5 Incorrect 345 ms 48204 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 8 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 9 ms 12268 KB Output is correct
6 Correct 9 ms 12396 KB Output is correct
7 Correct 9 ms 12396 KB Output is correct
8 Correct 10 ms 12544 KB Output is correct
9 Correct 10 ms 12396 KB Output is correct
10 Correct 10 ms 12396 KB Output is correct
11 Correct 10 ms 12396 KB Output is correct
12 Correct 10 ms 12396 KB Output is correct
13 Correct 9 ms 12396 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 8 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 9 ms 12268 KB Output is correct
6 Correct 9 ms 12396 KB Output is correct
7 Correct 9 ms 12396 KB Output is correct
8 Correct 10 ms 12544 KB Output is correct
9 Correct 10 ms 12396 KB Output is correct
10 Correct 153 ms 35316 KB Output is correct
11 Correct 201 ms 40544 KB Output is correct
12 Correct 198 ms 40160 KB Output is correct
13 Correct 209 ms 41652 KB Output is correct
14 Correct 186 ms 44000 KB Output is correct
15 Correct 10 ms 12396 KB Output is correct
16 Correct 10 ms 12396 KB Output is correct
17 Correct 10 ms 12396 KB Output is correct
18 Correct 9 ms 12396 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 8 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 12268 KB Output is correct
5 Correct 9 ms 12396 KB Output is correct
6 Correct 9 ms 12396 KB Output is correct
7 Correct 10 ms 12544 KB Output is correct
8 Correct 10 ms 12396 KB Output is correct
9 Correct 153 ms 35316 KB Output is correct
10 Correct 201 ms 40544 KB Output is correct
11 Correct 198 ms 40160 KB Output is correct
12 Correct 209 ms 41652 KB Output is correct
13 Correct 186 ms 44000 KB Output is correct
14 Correct 165 ms 35424 KB Output is correct
15 Correct 298 ms 42476 KB Output is correct
16 Correct 283 ms 41872 KB Output is correct
17 Correct 307 ms 43464 KB Output is correct
18 Correct 365 ms 45768 KB Output is correct
19 Correct 375 ms 47512 KB Output is correct
20 Correct 345 ms 49224 KB Output is correct
21 Incorrect 345 ms 48204 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 8 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 9 ms 12268 KB Output is correct
6 Correct 9 ms 12396 KB Output is correct
7 Correct 9 ms 12396 KB Output is correct
8 Correct 10 ms 12544 KB Output is correct
9 Correct 10 ms 12396 KB Output is correct
10 Correct 153 ms 35316 KB Output is correct
11 Correct 201 ms 40544 KB Output is correct
12 Correct 198 ms 40160 KB Output is correct
13 Correct 209 ms 41652 KB Output is correct
14 Correct 186 ms 44000 KB Output is correct
15 Correct 165 ms 35424 KB Output is correct
16 Correct 298 ms 42476 KB Output is correct
17 Correct 283 ms 41872 KB Output is correct
18 Correct 307 ms 43464 KB Output is correct
19 Correct 365 ms 45768 KB Output is correct
20 Correct 375 ms 47512 KB Output is correct
21 Correct 345 ms 49224 KB Output is correct
22 Incorrect 345 ms 48204 KB Output isn't correct
23 Halted 0 ms 0 KB -