oj.uz

Submission #331189

# Submission time Handle Problem Language Result Execution time Memory
331189 2020-11-27T16:53:53 Z arujbansal Swapping Cities (APIO20_swap) C++17
6 / 100
 373 ms 42056 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];
        
    assert(binlift[u][0] > -1);    
    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--;
    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 5 ms 6124 KB Output is correct
9 Correct 143 ms 28384 KB Output is correct
10 Correct 190 ms 33504 KB Output is correct
11 Correct 186 ms 32992 KB Output is correct
12 Correct 197 ms 34656 KB Output is correct
13 Correct 163 ms 36960 KB Output is correct
14 Correct 155 ms 28516 KB Output is correct
15 Correct 294 ms 35436 KB Output is correct
16 Correct 264 ms 34704 KB Output is correct
17 Correct 285 ms 36424 KB Output is correct
18 Correct 373 ms 38672 KB Output is correct
19 Correct 98 ms 13868 KB Output is correct
20 Correct 280 ms 36704 KB Output is correct
21 Correct 298 ms 35868 KB Output is correct
22 Correct 287 ms 37832 KB Output is correct
23 Correct 358 ms 40136 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 340 ms 40544 KB Output is correct
4 Correct 341 ms 42056 KB Output is correct
5 Incorrect 351 ms 41336 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 5 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 6 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 5 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 5 ms 6124 KB Output is correct
10 Correct 143 ms 28384 KB Output is correct
11 Correct 190 ms 33504 KB Output is correct
12 Correct 186 ms 32992 KB Output is correct
13 Correct 197 ms 34656 KB Output is correct
14 Correct 163 ms 36960 KB Output is correct
15 Correct 5 ms 6124 KB Output is correct
16 Correct 5 ms 6124 KB Output is correct
17 Correct 6 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 5 ms 6124 KB Output is correct
9 Correct 143 ms 28384 KB Output is correct
10 Correct 190 ms 33504 KB Output is correct
11 Correct 186 ms 32992 KB Output is correct
12 Correct 197 ms 34656 KB Output is correct
13 Correct 163 ms 36960 KB Output is correct
14 Correct 155 ms 28516 KB Output is correct
15 Correct 294 ms 35436 KB Output is correct
16 Correct 264 ms 34704 KB Output is correct
17 Correct 285 ms 36424 KB Output is correct
18 Correct 373 ms 38672 KB Output is correct
19 Correct 340 ms 40544 KB Output is correct
20 Correct 341 ms 42056 KB Output is correct
21 Incorrect 351 ms 41336 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 5 ms 6124 KB Output is correct
10 Correct 143 ms 28384 KB Output is correct
11 Correct 190 ms 33504 KB Output is correct
12 Correct 186 ms 32992 KB Output is correct
13 Correct 197 ms 34656 KB Output is correct
14 Correct 163 ms 36960 KB Output is correct
15 Correct 155 ms 28516 KB Output is correct
16 Correct 294 ms 35436 KB Output is correct
17 Correct 264 ms 34704 KB Output is correct
18 Correct 285 ms 36424 KB Output is correct
19 Correct 373 ms 38672 KB Output is correct
20 Correct 340 ms 40544 KB Output is correct
21 Correct 341 ms 42056 KB Output is correct
22 Incorrect 351 ms 41336 KB Output isn't correct
23 Halted 0 ms 0 KB -