oj.uz

Submission #969644

# Submission time Handle Problem Language Result Execution time Memory
969644 2024-04-25T11:55:06 Z LOLOLO Swapping Cities (APIO20_swap) C++17
7 / 100
 595 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) {
    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 0 ms 348 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 600 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 145 ms 41396 KB Output is correct
10 Correct 190 ms 51152 KB Output is correct
11 Correct 179 ms 50472 KB Output is correct
12 Correct 200 ms 52792 KB Output is correct
13 Runtime error 595 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 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 228 ms 45312 KB Output is correct
4 Correct 232 ms 48104 KB Output is correct
5 Correct 249 ms 46528 KB Output is correct
6 Correct 246 ms 47936 KB Output is correct
7 Correct 231 ms 47280 KB Output is correct
8 Correct 224 ms 44980 KB Output is correct
9 Correct 234 ms 46952 KB Output is correct
10 Correct 226 ms 44460 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 600 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 344 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 1 ms 856 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 344 KB Output is correct
2 Correct 0 ms 348 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 600 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 145 ms 41396 KB Output is correct
11 Correct 190 ms 51152 KB Output is correct
12 Correct 179 ms 50472 KB Output is correct
13 Correct 200 ms 52792 KB Output is correct
14 Runtime error 595 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 0 ms 348 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 600 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 145 ms 41396 KB Output is correct
10 Correct 190 ms 51152 KB Output is correct
11 Correct 179 ms 50472 KB Output is correct
12 Correct 200 ms 52792 KB Output is correct
13 Runtime error 595 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 344 KB Output is correct
2 Correct 0 ms 348 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 600 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 145 ms 41396 KB Output is correct
11 Correct 190 ms 51152 KB Output is correct
12 Correct 179 ms 50472 KB Output is correct
13 Correct 200 ms 52792 KB Output is correct
14 Runtime error 595 ms 524288 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -