oj.uz

Submission #331322

# Submission time Handle Problem Language Result Execution time Memory
331322 2020-11-28T02:35:36 Z arujbansal Swapping Cities (APIO20_swap) C++17
6 / 100
 423 ms 58312 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 = 6e5 + 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 = 22;
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++)
        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 (!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] = fakeNode;
        }
    }

    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 13 ms 16676 KB Output is correct
2 Correct 11 ms 16748 KB Output is correct
3 Correct 11 ms 16748 KB Output is correct
4 Correct 12 ms 16940 KB Output is correct
5 Correct 16 ms 17132 KB Output is correct
6 Correct 13 ms 17152 KB Output is correct
7 Correct 14 ms 17132 KB Output is correct
8 Correct 15 ms 17132 KB Output is correct
9 Correct 178 ms 42464 KB Output is correct
10 Correct 208 ms 47968 KB Output is correct
11 Correct 207 ms 47456 KB Output is correct
12 Correct 218 ms 49248 KB Output is correct
13 Correct 187 ms 51680 KB Output is correct
14 Correct 173 ms 42592 KB Output is correct
15 Correct 336 ms 52332 KB Output is correct
16 Correct 310 ms 51600 KB Output is correct
17 Correct 327 ms 53320 KB Output is correct
18 Correct 394 ms 55736 KB Output is correct
19 Correct 120 ms 27052 KB Output is correct
20 Correct 320 ms 52960 KB Output is correct
21 Correct 316 ms 51996 KB Output is correct
22 Correct 338 ms 53576 KB Output is correct
23 Correct 423 ms 55880 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16676 KB Output is correct
2 Correct 11 ms 16748 KB Output is correct
3 Correct 369 ms 56936 KB Output is correct
4 Correct 372 ms 58312 KB Output is correct
5 Incorrect 389 ms 57592 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16748 KB Output is correct
2 Correct 13 ms 16676 KB Output is correct
3 Correct 11 ms 16748 KB Output is correct
4 Correct 11 ms 16748 KB Output is correct
5 Correct 12 ms 16940 KB Output is correct
6 Correct 16 ms 17132 KB Output is correct
7 Correct 13 ms 17152 KB Output is correct
8 Correct 14 ms 17132 KB Output is correct
9 Correct 15 ms 17132 KB Output is correct
10 Correct 178 ms 42464 KB Output is correct
11 Correct 208 ms 47968 KB Output is correct
12 Correct 207 ms 47456 KB Output is correct
13 Correct 218 ms 49248 KB Output is correct
14 Correct 187 ms 51680 KB Output is correct
15 Correct 12 ms 17132 KB Output is correct
16 Correct 12 ms 17132 KB Output is correct
17 Correct 13 ms 17132 KB Output is correct
18 Correct 12 ms 17132 KB Output is correct
19 Correct 12 ms 17132 KB Output is correct
20 Incorrect 12 ms 17132 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16676 KB Output is correct
2 Correct 11 ms 16748 KB Output is correct
3 Correct 11 ms 16748 KB Output is correct
4 Correct 12 ms 16940 KB Output is correct
5 Correct 16 ms 17132 KB Output is correct
6 Correct 13 ms 17152 KB Output is correct
7 Correct 14 ms 17132 KB Output is correct
8 Correct 15 ms 17132 KB Output is correct
9 Correct 178 ms 42464 KB Output is correct
10 Correct 208 ms 47968 KB Output is correct
11 Correct 207 ms 47456 KB Output is correct
12 Correct 218 ms 49248 KB Output is correct
13 Correct 187 ms 51680 KB Output is correct
14 Correct 173 ms 42592 KB Output is correct
15 Correct 336 ms 52332 KB Output is correct
16 Correct 310 ms 51600 KB Output is correct
17 Correct 327 ms 53320 KB Output is correct
18 Correct 394 ms 55736 KB Output is correct
19 Correct 369 ms 56936 KB Output is correct
20 Correct 372 ms 58312 KB Output is correct
21 Incorrect 389 ms 57592 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16748 KB Output is correct
2 Correct 13 ms 16676 KB Output is correct
3 Correct 11 ms 16748 KB Output is correct
4 Correct 11 ms 16748 KB Output is correct
5 Correct 12 ms 16940 KB Output is correct
6 Correct 16 ms 17132 KB Output is correct
7 Correct 13 ms 17152 KB Output is correct
8 Correct 14 ms 17132 KB Output is correct
9 Correct 15 ms 17132 KB Output is correct
10 Correct 178 ms 42464 KB Output is correct
11 Correct 208 ms 47968 KB Output is correct
12 Correct 207 ms 47456 KB Output is correct
13 Correct 218 ms 49248 KB Output is correct
14 Correct 187 ms 51680 KB Output is correct
15 Correct 173 ms 42592 KB Output is correct
16 Correct 336 ms 52332 KB Output is correct
17 Correct 310 ms 51600 KB Output is correct
18 Correct 327 ms 53320 KB Output is correct
19 Correct 394 ms 55736 KB Output is correct
20 Correct 369 ms 56936 KB Output is correct
21 Correct 372 ms 58312 KB Output is correct
22 Incorrect 389 ms 57592 KB Output isn't correct
23 Halted 0 ms 0 KB -