oj.uz

Submission #331163

# Submission time Handle Problem Language Result Execution time Memory
331163 2020-11-27T16:05:52 Z arujbansal Swapping Cities (APIO20_swap) C++17
0 / 100
 326 ms 41416 KB 
#ifndef arujbansal_local
#include "swap.h"
#endif

#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 par, compSize;
vi g[MAXN];
int 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) {
    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);
        valid[fakeNode++] = true;
        return;
    }

    addEdge(u, w);
    addEdge(v, w);
    fakeNode++;

    if (compSize[u] < compSize[v]) swap(u, v);

    compSize[u] += compSize[v];
    par[v] = u;
}

void dfs(int u = 0, 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
    par.resize(n);
    iota(all(par), 0);
    compSize.assign(n, 1);
    fakeNode = n;

    for (const auto &[u, v, w] : edges)
        unite(u, v, w);

    dfs();
}

int getMinimumFuelCapacity(int X, int Y) {
    int lca = queryLCA(X, Y);

    return (valid[lca] ? 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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5108 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5228 KB Output is correct
5 Correct 5 ms 5356 KB Output is correct
6 Correct 5 ms 5356 KB Output is correct
7 Correct 5 ms 5356 KB Output is correct
8 Correct 5 ms 5356 KB Output is correct
9 Correct 153 ms 30048 KB Output is correct
10 Correct 195 ms 35808 KB Output is correct
11 Correct 199 ms 35188 KB Output is correct
12 Correct 227 ms 36960 KB Output is correct
13 Correct 140 ms 37108 KB Output is correct
14 Correct 166 ms 30452 KB Output is correct
15 Correct 326 ms 40064 KB Output is correct
16 Correct 307 ms 39184 KB Output is correct
17 Correct 311 ms 41032 KB Output is correct
18 Correct 268 ms 41416 KB Output is correct
19 Incorrect 106 ms 14124 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5108 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Incorrect 266 ms 38764 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5100 KB Output isn't correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5100 KB Output isn't correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5108 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5228 KB Output is correct
5 Correct 5 ms 5356 KB Output is correct
6 Correct 5 ms 5356 KB Output is correct
7 Correct 5 ms 5356 KB Output is correct
8 Correct 5 ms 5356 KB Output is correct
9 Correct 153 ms 30048 KB Output is correct
10 Correct 195 ms 35808 KB Output is correct
11 Correct 199 ms 35188 KB Output is correct
12 Correct 227 ms 36960 KB Output is correct
13 Correct 140 ms 37108 KB Output is correct
14 Correct 166 ms 30452 KB Output is correct
15 Correct 326 ms 40064 KB Output is correct
16 Correct 307 ms 39184 KB Output is correct
17 Correct 311 ms 41032 KB Output is correct
18 Correct 268 ms 41416 KB Output is correct
19 Incorrect 266 ms 38764 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5100 KB Output isn't correct