oj.uz

Submission #969646

# Submission time Handle Problem Language Result Execution time Memory
969646 2024-04-25T12:00:09 Z LOLOLO Swapping Cities (APIO20_swap) C++17
7 / 100
 590 ms 524288 KB 
#include <bits/stdc++.h>
#include "swap.h"
#define ll long long
using namespace std;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 3e5 + 50;
int a[N];

struct dsu{
    int curn = -1;
    vector <int> sz, par, line, cost, st, en, degree;
    vector < vector <int>> in, p, cc;
    vector < vector <pair <int, int>>> ed;
    int dfstimer = 1;

    void prepare(int n) {
        in.clear();
        p.clear();
        cc.clear();

        for (int i = 0; i <= curn; i++) {
            ed[i].clear();
        }

        curn = n;
        sz.assign(n + 1, 1);
        par.assign(n + 1, 0);
        line.assign(n + 1, 1);
        cost.assign(n + 1, 1e9 + 10);
        st.assign(n + 1, 0);
        en.assign(n + 1, 0);
        degree.assign(n + 1, 0);
        in.resize(n + 1);
        ed.resize(n + 1);

        for (int i = 0; i <= n; i++) {
            in[i].pb(i);
            p.pb(vector <int> (20, 0));
            cc.pb(vector <int> (20, 0));
        }
    }

    int get(int a) {
        return par[a] ? get(par[a]) : a;
    }

    void dfs(int u, int v) {
        st[u] = ++dfstimer;
        p[u][0] = v;
        for (int j = 1; j < 20; j++) {
            p[u][j] = p[p[u][j - 1]][j - 1];
            cc[u][j] = max(cc[u][j - 1], cc[p[u][j - 1]][j - 1]);
        }

        for (auto x : ed[u]) {
            if (x.f == v)
                continue;

            cc[x.f][0] = x.s;
            dfs(x.f, u);
        }

        en[u] = dfstimer;
    }

    bool is(int a, int b) {
        return st[a] <= st[b] && en[a] >= st[b];
    }

    int lca(int a, int b) {
        if (is(a, b))
            return a;

        if (is(b, a))
            return b;

        for (int j = 19; j >= 0; j--) {
            if (is(p[a][j], b) == 0)
                a = p[a][j];
        }

        return p[a][0];
    }

    int answer(int a, int b) {
        int c = lca(a, b), ans = max(cost[a], cost[b]);
        for (int j = 19; j >= 0; j--) {
            if (p[a][j] != c && is(c, p[a][j])) {
                ans = max(ans, cc[a][j]);
                a = p[a][j];
            }

            if (p[b][j] != c && is(c, p[b][j])) {
                ans = max(ans, cc[b][j]);
                b = p[b][j];
            }
        }

        return ans;
    }

    void unite(int a, int b, int w) {
        degree[a]++;
        degree[b]++;
        int mx = max(degree[a], degree[b]);

        a = get(a), b = get(b);
        if (a == b) {
            line[a] = 0;
            for (auto x : in[a]) {
                cost[x] = w;
            }

            in[a].clear();
            return;
        }

        ed[a].pb({b, w});
        ed[b].pb({a, w});
        if (sz[a] < sz[b])
            swap(a, b);

        par[b] = a;
        line[a] = line[a] & line[b];
        if (mx > 2) {
            line[a] = 0; 
        }

        for (auto x : in[b])
            in[a].pb(x);

        if (line[a] == 0) {
            for (auto x : in[a]) {
                cost[x] = w;
            }
            in[a].clear();
        }
    }
} D;

void init(int n, int m, vector <int> u, vector <int> v, vector <int> w) {
    dsu D1;
    D = D1;
    D.prepare(n);
    vector < vector <int>> edge;
    for (int i = 0; i < m; i++) {
        edge.pb({w[i], u[i] + 1, v[i] + 1});
    }

    sort(all(edge));
    for (auto x : edge) {
        D.unite(x[1], x[2], x[0]);
    }

    D.dfs(1, 1);
}

int getMinimumFuelCapacity(int a, int b) {
    a++;
    b++;
    int ans = D.answer(a, b);
    if (ans > 1e9)
        return -1;

    return ans;
}

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1
--------------------------------------------------|
3 2
0 1 5
0 2 5
1
1 2
--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|
3

10
4
--------------------------------------------------|
-1
--------------------------------------------------|
==================================================+
*/

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 2 ms 1372 KB Output is correct
9 Correct 153 ms 41904 KB Output is correct
10 Correct 186 ms 50348 KB Output is correct
11 Correct 193 ms 49992 KB Output is correct
12 Correct 210 ms 52656 KB Output is correct
13 Runtime error 590 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 245 ms 46136 KB Output is correct
4 Correct 238 ms 47540 KB Output is correct
5 Correct 246 ms 46512 KB Output is correct
6 Correct 235 ms 48048 KB Output is correct
7 Correct 247 ms 46984 KB Output is correct
8 Correct 224 ms 44976 KB Output is correct
9 Correct 244 ms 47188 KB Output is correct
10 Correct 250 ms 44972 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 2 ms 1372 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Incorrect 1 ms 604 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 2 ms 1372 KB Output is correct
10 Correct 153 ms 41904 KB Output is correct
11 Correct 186 ms 50348 KB Output is correct
12 Correct 193 ms 49992 KB Output is correct
13 Correct 210 ms 52656 KB Output is correct
14 Runtime error 590 ms 524288 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 2 ms 1372 KB Output is correct
9 Correct 153 ms 41904 KB Output is correct
10 Correct 186 ms 50348 KB Output is correct
11 Correct 193 ms 49992 KB Output is correct
12 Correct 210 ms 52656 KB Output is correct
13 Runtime error 590 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 2 ms 1372 KB Output is correct
10 Correct 153 ms 41904 KB Output is correct
11 Correct 186 ms 50348 KB Output is correct
12 Correct 193 ms 49992 KB Output is correct
13 Correct 210 ms 52656 KB Output is correct
14 Runtime error 590 ms 524288 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -