oj.uz

Submission #564987

# Submission time Handle Problem Language Result Execution time Memory
564987 2022-05-20T06:47:18 Z Ooops_sorry Swapping Cities (APIO20_swap) C++14
0 / 100
 2000 ms 66652 KB 
#include<bits/stdc++.h>
#ifndef LOCAL
    #include "swap.h"
#endif // LOCAL

using namespace std;

#define pb push_back
#define ld long double
#define ll long long

mt19937 rnd(51);

struct vert {
    int u, mn, mx;
};

const int N = 2e5 + 10, INF = 1e9;
multiset<int> st[N];
vector<pair<int,int>> g[N];
int val[N], d[N], ed[N];
vert po[20][N];

struct dsu {
    vector<int> par, sz;
    dsu(int n) {
        par.resize(n);
        iota(par.begin(), par.end(), 0);
        sz.resize(n, 1);
    }
    int find_set(int v) {
        if (v == par[v]) return v;
        else return par[v] = find_set(par[v]);
    }
    bool union_set(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if (a == b) return 0;
        if (sz[a] < sz[b]) {
            swap(a, b);
        }
        par[b] = a;
        sz[a] += sz[b];
        return 1;
    }
};

void dfs(int v, int p) {
    for (auto to : g[v]) {
        if (to.first != p) {
            d[to.first] = d[v] + 1;
            po[0][to.first] = {v, val[to.first], to.second};
            ed[to.first] = to.second;
            dfs(to.first, v);
        }
    }
}

int lca(int a, int b) {
    if (d[a] < d[b]) swap(a, b);
    for (int i = 19; i >= 0; i--) {
        if (d[po[i][a].u] >= d[b]) {
            a = po[i][a].u;
        }
    }
    if (a == b) return a;
    for (int i = 19; i >= 0; i--) {
        if (po[i][a].u != po[i][b].u) {
            a = po[i][a].u;
            b = po[i][b].u;
        }
    }
    return po[0][a].u;
}

void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
    dsu d(n);
    vector<int> ord(m);
    for (int i = 0; i < n; i++) {
        st[i].insert(INF);
    }
    for (int i = 0; i < m; i++) {
        st[u[i]].insert(w[i]);
        st[v[i]].insert(w[i]);
    }
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j){return w[i] < w[j];});
    for (auto i : ord) {
        if (d.union_set(u[i], v[i])) {
            st[u[i]].erase(st[u[i]].find(w[i]));
            st[v[i]].erase(st[v[i]].find(w[i]));
            g[u[i]].pb({v[i], w[i]});
            g[v[i]].pb({u[i], w[i]});
        }
    }
    for (int i = 0; i < n; i++) {
        val[i] = *st[i].begin();
    }
    dfs(0, 0);
    po[0][0] = {0, val[0], -INF};
    for (int i = 1; i < 20; i++) {
        for (int j = 0; j < n; j++) {
            int v = po[i - 1][j].u;
            po[i][j] = {po[i - 1][v].u, min(po[i - 1][j].mn, po[i - 1][v].mn), max(po[i - 1][j].mx, po[i - 1][v].mx)};
        }
    }
}

int getMinimumFuelCapacity(int x, int y) {
    assert(x != y);
    int mn = INF, mx = -INF, g = lca(x, y);
    mn = val[g];
    while (x != g) {
        mx = max(mx, ed[x]);
        mn = min(mn, val[x]);
        x = po[0][x].u;
    }
    while (y != g) {
        mx = max(mx, ed[y]);
        mn = min(mn, val[y]);
        y = po[0][y].u;
    }
    if (mn == INF)  return -1;
    return max(mn, mx);
}

#ifdef LOCAL

signed main() {
    int N, M;
    assert(2 == scanf("%d %d", &N, &M));
    std::vector<int> U(M), V(M), W(M);
    for (int i = 0; i < M; ++i) {
    assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
    }
    int Q;
    assert(1 == scanf("%d", &Q));
    std::vector<int> X(Q), Y(Q);
    for (int i = 0; i < Q; ++i) {
    assert(2 == scanf("%d %d", &X[i], &Y[i]));
    }
    init(N, M, U, V, W);
    std::vector<int> minimum_fuel_capacities(Q);
    for (int i = 0; i < Q; ++i) {
    minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
    }
    for (int i = 0; i < Q; ++i) {
    printf("%d\n", minimum_fuel_capacities[i]);
    }
    return 0;
}

#endif

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14548 KB Output is correct
2 Correct 9 ms 14548 KB Output is correct
3 Correct 7 ms 14548 KB Output is correct
4 Correct 8 ms 14800 KB Output is correct
5 Correct 10 ms 15012 KB Output is correct
6 Correct 9 ms 14932 KB Output is correct
7 Correct 11 ms 14928 KB Output is correct
8 Correct 9 ms 15060 KB Output is correct
9 Correct 219 ms 53248 KB Output is correct
10 Correct 232 ms 62992 KB Output is correct
11 Correct 238 ms 61824 KB Output is correct
12 Correct 286 ms 64988 KB Output is correct
13 Correct 209 ms 66652 KB Output is correct
14 Execution timed out 2076 ms 52832 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14548 KB Output is correct
2 Correct 9 ms 14548 KB Output is correct
3 Incorrect 626 ms 60748 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14548 KB Output is correct
2 Correct 9 ms 14548 KB Output is correct
3 Correct 7 ms 14548 KB Output is correct
4 Correct 8 ms 14800 KB Output is correct
5 Correct 10 ms 15012 KB Output is correct
6 Correct 9 ms 14932 KB Output is correct
7 Correct 11 ms 14928 KB Output is correct
8 Correct 9 ms 15060 KB Output is correct
9 Correct 8 ms 14548 KB Output is correct
10 Incorrect 9 ms 14932 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14548 KB Output is correct
2 Correct 8 ms 14548 KB Output is correct
3 Correct 9 ms 14548 KB Output is correct
4 Correct 7 ms 14548 KB Output is correct
5 Correct 8 ms 14800 KB Output is correct
6 Correct 10 ms 15012 KB Output is correct
7 Correct 9 ms 14932 KB Output is correct
8 Correct 11 ms 14928 KB Output is correct
9 Correct 9 ms 15060 KB Output is correct
10 Correct 219 ms 53248 KB Output is correct
11 Correct 232 ms 62992 KB Output is correct
12 Correct 238 ms 61824 KB Output is correct
13 Correct 286 ms 64988 KB Output is correct
14 Correct 209 ms 66652 KB Output is correct
15 Incorrect 9 ms 14932 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14548 KB Output is correct
2 Correct 9 ms 14548 KB Output is correct
3 Correct 7 ms 14548 KB Output is correct
4 Correct 8 ms 14800 KB Output is correct
5 Correct 10 ms 15012 KB Output is correct
6 Correct 9 ms 14932 KB Output is correct
7 Correct 11 ms 14928 KB Output is correct
8 Correct 9 ms 15060 KB Output is correct
9 Correct 219 ms 53248 KB Output is correct
10 Correct 232 ms 62992 KB Output is correct
11 Correct 238 ms 61824 KB Output is correct
12 Correct 286 ms 64988 KB Output is correct
13 Correct 209 ms 66652 KB Output is correct
14 Execution timed out 2076 ms 52832 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14548 KB Output is correct
2 Correct 8 ms 14548 KB Output is correct
3 Correct 9 ms 14548 KB Output is correct
4 Correct 7 ms 14548 KB Output is correct
5 Correct 8 ms 14800 KB Output is correct
6 Correct 10 ms 15012 KB Output is correct
7 Correct 9 ms 14932 KB Output is correct
8 Correct 11 ms 14928 KB Output is correct
9 Correct 9 ms 15060 KB Output is correct
10 Correct 219 ms 53248 KB Output is correct
11 Correct 232 ms 62992 KB Output is correct
12 Correct 238 ms 61824 KB Output is correct
13 Correct 286 ms 64988 KB Output is correct
14 Correct 209 ms 66652 KB Output is correct
15 Execution timed out 2076 ms 52832 KB Time limit exceeded
16 Halted 0 ms 0 KB -