oj.uz

Submission #564374

# Submission time Handle Problem Language Result Execution time Memory
564374 2022-05-19T05:02:41 Z ngpin04 Swapping Cities (APIO20_swap) C++14
13 / 100
 740 ms 58140 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
  if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
  if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
  return l + rd() % (r - l + 1);
}
const int N = 2e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

vector <int> adj[N];

int max_e[N][20];
int ok_e[N][20];
int ok_v[N][20];
int anc[N][20];
int par[N];
int deg[N];
int fr[N];
int to[N];
int w[N];
int h[N];
int n,m;

bool notmst[N];

int getpar(int u) {
    return (par[u] < 0) ? u : (par[u] = getpar(par[u]));
}

bool join(int u, int v) {
    u = getpar(u);
    v = getpar(v);
    if (u == v)
        return false;
    if (par[u] > par[v])
        swap(u, v);
    par[u] += par[v];
    par[v] = u;
    return true;
}

int getlca(int u, int v) {
    if (h[u] > h[v])
        swap(u, v);

    for (int i = 19; i >= 0; i--) 
        if (h[v] - bit(i) >= h[u])
            v = anc[v][i];
    if (u == v)
        return v;

    for (int i = 19; i >= 0; i--) if (anc[u][i] != anc[v][i]) {
        u = anc[u][i];
        v = anc[v][i];
    }
    return anc[v][0];
}

void dfs(int u, int p = -1) {
    anc[u][0] = p;

    for (int i : adj[u]) {
        int v = fr[i] ^ to[i] ^ u;
        if (v == p)
            continue;
        h[v] = h[u] + 1;
        max_e[v][0] = w[i];
        dfs(v, u);
    }
}

void build() {
    vector <int> ind(m, 0);
    iota(ALL(ind), 0);
    sort(ALL(ind), [](int i, int j) {
        return w[i] < w[j];
    });

    for (int i = 0; i < n; i++)
        par[i] = -1;

    for (int i : ind) {
        if (join(fr[i], to[i])) {
            adj[fr[i]].push_back(i);
            adj[to[i]].push_back(i);
        } else 
            notmst[i] = true;
    }

    dfs(0);

    for (int j = 1; j < 20; j++)
    for (int i = 0; i < n; i++) {
        int p = anc[i][j - 1];
        anc[i][j] = (p < 0) ? -1 : (anc[p][j - 1]);
    }

    for (int i = 0; i < n; i++) {
        par[i] = -1;
        ok_v[i][0] = ok_e[i][0] = 2 * oo;
    }
    max_e[0][0] = 2 * oo;

    for (int it : ind) if (notmst[it]) {
        int u = fr[it];
        int v = to[it];
        int p = getlca(u, v);

        for (int i = getpar(u); h[i] > h[p]; i = getpar(i)) {
            ok_e[i][0] = w[it];
            par[i] = anc[i][0];
        }   

        for (int i = getpar(v); h[i] > h[p]; i = getpar(i)) {
            ok_e[i][0] = w[it];
            par[i] = anc[i][0];
        }
    }

    for (int it : ind) {
        int u = fr[it];
        int v = to[it];
        deg[u]++;
        deg[v]++;
        if (deg[u] == 3)
            ok_v[u][0] = w[it];
        if (deg[v] == 3) 
            ok_v[v][0] = w[it];
    }

    for (int j = 1; j < 20; j++) 
    for (int i = 0; i < n; i++) {
        int p = anc[i][j - 1];
        if (p < 0) {
            max_e[i][j] = ok_v[i][j] = ok_e[i][j] = 2 * oo;
        } else {
            ok_v[i][j] = min(ok_v[i][j - 1], ok_v[p][j - 1]);
            ok_e[i][j] = min(ok_e[i][j - 1], ok_e[p][j - 1]);
            max_e[i][j] = max(max_e[i][j - 1], max_e[p][j - 1]);
        }
    }
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    n = N;
    m = M;
    for (int i = 0; i < m; i++) {
        fr[i] = U[i];
        to[i] = V[i];
        w[i] = W[i];
    }
    build();
}

int getmax(int u, int p) {
    int res = 0;
    for (int i = 19; i >= 0; i--) if (h[u] - bit(i) >= h[p]) {
        maxi(res, max_e[u][i]);
        u = anc[u][i];
    }
    return res;
}

int minEdge(int u, int p) {
    int res = 2 * oo;
    for (int i = 19; i >= 0; i--) if (h[u] - bit(i) >= h[p]) {
        mini(res, ok_e[u][i]);
        u = anc[u][i];
    }
    return res;
}

int minVertex(int u, int p) {
    int res = 2 * oo;
    u = anc[u][0];  
    for (int i = 19; i >= 0; i--) if (h[u] - bit(i) > h[p]) {
        mini(res, ok_v[u][i]);
        u = anc[u][i];
    }
    return res;
}

int getMinimumFuelCapacity(int u, int v) {
    if (h[u] > h[v])
        swap(u, v);
    int p = getlca(u, v);
    int res = max(getmax(u, p), getmax(v, p));
    int ed = min(minEdge(u, p), minEdge(v, p));
    int vt = min(minVertex(u, p), minVertex(v, p));
    if (v != p)
        mini(vt, ok_v[p][0]);

    // cerr << u << " " << v << " " << vt << " " << ed << "\n";
    maxi(res, min(vt, ed));
    if (res == 2 * oo)
        res = -1;
    return res;
}

#include "swap.h"
//#include "grader.cpp"

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4960 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5148 KB Output is correct
5 Correct 4 ms 5408 KB Output is correct
6 Correct 4 ms 5460 KB Output is correct
7 Correct 4 ms 5460 KB Output is correct
8 Correct 4 ms 5460 KB Output is correct
9 Correct 144 ms 41420 KB Output is correct
10 Correct 183 ms 50920 KB Output is correct
11 Correct 202 ms 49688 KB Output is correct
12 Correct 183 ms 52628 KB Output is correct
13 Correct 178 ms 54480 KB Output is correct
14 Correct 187 ms 40980 KB Output is correct
15 Correct 668 ms 54732 KB Output is correct
16 Correct 719 ms 51992 KB Output is correct
17 Correct 687 ms 58140 KB Output is correct
18 Correct 740 ms 56848 KB Output is correct
19 Correct 195 ms 17868 KB Output is correct
20 Correct 683 ms 55120 KB Output is correct
21 Correct 722 ms 52892 KB Output is correct
22 Correct 717 ms 57228 KB Output is correct
23 Correct 724 ms 57576 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4960 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 324 ms 49216 KB Output is correct
4 Correct 310 ms 51312 KB Output is correct
5 Correct 301 ms 50276 KB Output is correct
6 Correct 315 ms 51052 KB Output is correct
7 Correct 316 ms 50732 KB Output is correct
8 Correct 322 ms 49044 KB Output is correct
9 Correct 302 ms 50300 KB Output is correct
10 Correct 306 ms 48628 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4960 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5148 KB Output is correct
5 Correct 4 ms 5408 KB Output is correct
6 Correct 4 ms 5460 KB Output is correct
7 Correct 4 ms 5460 KB Output is correct
8 Correct 4 ms 5460 KB Output is correct
9 Correct 4 ms 5076 KB Output is correct
10 Correct 4 ms 5428 KB Output is correct
11 Correct 4 ms 5408 KB Output is correct
12 Correct 4 ms 5460 KB Output is correct
13 Correct 4 ms 5332 KB Output is correct
14 Correct 4 ms 5332 KB Output is correct
15 Incorrect 4 ms 5460 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 5076 KB Output is correct
2 Correct 3 ms 4960 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5148 KB Output is correct
6 Correct 4 ms 5408 KB Output is correct
7 Correct 4 ms 5460 KB Output is correct
8 Correct 4 ms 5460 KB Output is correct
9 Correct 4 ms 5460 KB Output is correct
10 Correct 144 ms 41420 KB Output is correct
11 Correct 183 ms 50920 KB Output is correct
12 Correct 202 ms 49688 KB Output is correct
13 Correct 183 ms 52628 KB Output is correct
14 Correct 178 ms 54480 KB Output is correct
15 Correct 4 ms 5428 KB Output is correct
16 Correct 4 ms 5408 KB Output is correct
17 Correct 4 ms 5460 KB Output is correct
18 Correct 4 ms 5332 KB Output is correct
19 Correct 4 ms 5332 KB Output is correct
20 Incorrect 4 ms 5460 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4960 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5148 KB Output is correct
5 Correct 4 ms 5408 KB Output is correct
6 Correct 4 ms 5460 KB Output is correct
7 Correct 4 ms 5460 KB Output is correct
8 Correct 4 ms 5460 KB Output is correct
9 Correct 144 ms 41420 KB Output is correct
10 Correct 183 ms 50920 KB Output is correct
11 Correct 202 ms 49688 KB Output is correct
12 Correct 183 ms 52628 KB Output is correct
13 Correct 178 ms 54480 KB Output is correct
14 Correct 187 ms 40980 KB Output is correct
15 Correct 668 ms 54732 KB Output is correct
16 Correct 719 ms 51992 KB Output is correct
17 Correct 687 ms 58140 KB Output is correct
18 Correct 740 ms 56848 KB Output is correct
19 Correct 324 ms 49216 KB Output is correct
20 Correct 310 ms 51312 KB Output is correct
21 Correct 301 ms 50276 KB Output is correct
22 Correct 315 ms 51052 KB Output is correct
23 Correct 316 ms 50732 KB Output is correct
24 Correct 322 ms 49044 KB Output is correct
25 Correct 302 ms 50300 KB Output is correct
26 Correct 306 ms 48628 KB Output is correct
27 Correct 4 ms 5428 KB Output is correct
28 Correct 4 ms 5408 KB Output is correct
29 Correct 4 ms 5460 KB Output is correct
30 Correct 4 ms 5332 KB Output is correct
31 Correct 4 ms 5332 KB Output is correct
32 Incorrect 4 ms 5460 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5076 KB Output is correct
2 Correct 3 ms 4960 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5148 KB Output is correct
6 Correct 4 ms 5408 KB Output is correct
7 Correct 4 ms 5460 KB Output is correct
8 Correct 4 ms 5460 KB Output is correct
9 Correct 4 ms 5460 KB Output is correct
10 Correct 144 ms 41420 KB Output is correct
11 Correct 183 ms 50920 KB Output is correct
12 Correct 202 ms 49688 KB Output is correct
13 Correct 183 ms 52628 KB Output is correct
14 Correct 178 ms 54480 KB Output is correct
15 Correct 187 ms 40980 KB Output is correct
16 Correct 668 ms 54732 KB Output is correct
17 Correct 719 ms 51992 KB Output is correct
18 Correct 687 ms 58140 KB Output is correct
19 Correct 740 ms 56848 KB Output is correct
20 Correct 324 ms 49216 KB Output is correct
21 Correct 310 ms 51312 KB Output is correct
22 Correct 301 ms 50276 KB Output is correct
23 Correct 315 ms 51052 KB Output is correct
24 Correct 316 ms 50732 KB Output is correct
25 Correct 322 ms 49044 KB Output is correct
26 Correct 302 ms 50300 KB Output is correct
27 Correct 306 ms 48628 KB Output is correct
28 Correct 4 ms 5428 KB Output is correct
29 Correct 4 ms 5408 KB Output is correct
30 Correct 4 ms 5460 KB Output is correct
31 Correct 4 ms 5332 KB Output is correct
32 Correct 4 ms 5332 KB Output is correct
33 Incorrect 4 ms 5460 KB Output isn't correct
34 Halted 0 ms 0 KB -