oj.uz

Submission #331186

# Submission time Handle Problem Language Result Execution time Memory
331186 2020-11-27T16:50:29 Z arujbansal Swapping Cities (APIO20_swap) C++17
6 / 100
 349 ms 45896 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 = 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);

    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;
        }
    }

    fakeNode--;
    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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 6124 KB Output is correct
8 Correct 6 ms 6124 KB Output is correct
9 Correct 144 ms 28624 KB Output is correct
10 Correct 181 ms 33760 KB Output is correct
11 Correct 186 ms 33376 KB Output is correct
12 Correct 192 ms 34784 KB Output is correct
13 Correct 162 ms 37136 KB Output is correct
14 Correct 154 ms 28768 KB Output is correct
15 Correct 281 ms 35820 KB Output is correct
16 Correct 264 ms 34704 KB Output is correct
17 Correct 293 ms 36424 KB Output is correct
18 Correct 336 ms 38728 KB Output is correct
19 Correct 86 ms 14028 KB Output is correct
20 Correct 293 ms 41184 KB Output is correct
21 Correct 272 ms 40316 KB Output is correct
22 Correct 290 ms 42340 KB Output is correct
23 Correct 349 ms 44488 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5868 KB Output is correct
2 Correct 4 ms 5868 KB Output is correct
3 Correct 328 ms 40580 KB Output is correct
4 Correct 334 ms 45896 KB Output is correct
5 Incorrect 335 ms 45176 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 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 6124 KB Output is correct
9 Correct 6 ms 6124 KB Output is correct
10 Correct 5 ms 6124 KB Output is correct
11 Correct 5 ms 6124 KB Output is correct
12 Correct 5 ms 6124 KB Output is correct
13 Correct 5 ms 6124 KB Output is correct
14 Correct 5 ms 6124 KB Output is correct
15 Incorrect 5 ms 6124 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 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 6124 KB Output is correct
9 Correct 6 ms 6124 KB Output is correct
10 Correct 144 ms 28624 KB Output is correct
11 Correct 181 ms 33760 KB Output is correct
12 Correct 186 ms 33376 KB Output is correct
13 Correct 192 ms 34784 KB Output is correct
14 Correct 162 ms 37136 KB Output is correct
15 Correct 5 ms 6124 KB Output is correct
16 Correct 5 ms 6124 KB Output is correct
17 Correct 5 ms 6124 KB Output is correct
18 Correct 5 ms 6124 KB Output is correct
19 Correct 5 ms 6124 KB Output is correct
20 Incorrect 5 ms 6124 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 6124 KB Output is correct
8 Correct 6 ms 6124 KB Output is correct
9 Correct 144 ms 28624 KB Output is correct
10 Correct 181 ms 33760 KB Output is correct
11 Correct 186 ms 33376 KB Output is correct
12 Correct 192 ms 34784 KB Output is correct
13 Correct 162 ms 37136 KB Output is correct
14 Correct 154 ms 28768 KB Output is correct
15 Correct 281 ms 35820 KB Output is correct
16 Correct 264 ms 34704 KB Output is correct
17 Correct 293 ms 36424 KB Output is correct
18 Correct 336 ms 38728 KB Output is correct
19 Correct 328 ms 40580 KB Output is correct
20 Correct 334 ms 45896 KB Output is correct
21 Incorrect 335 ms 45176 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 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 6124 KB Output is correct
9 Correct 6 ms 6124 KB Output is correct
10 Correct 144 ms 28624 KB Output is correct
11 Correct 181 ms 33760 KB Output is correct
12 Correct 186 ms 33376 KB Output is correct
13 Correct 192 ms 34784 KB Output is correct
14 Correct 162 ms 37136 KB Output is correct
15 Correct 154 ms 28768 KB Output is correct
16 Correct 281 ms 35820 KB Output is correct
17 Correct 264 ms 34704 KB Output is correct
18 Correct 293 ms 36424 KB Output is correct
19 Correct 336 ms 38728 KB Output is correct
20 Correct 328 ms 40580 KB Output is correct
21 Correct 334 ms 45896 KB Output is correct
22 Incorrect 335 ms 45176 KB Output isn't correct
23 Halted 0 ms 0 KB -