oj.uz

Submission #969674

# Submission time Handle Problem Language Result Execution time Memory
969674 2024-04-25T13:03:10 Z LOLOLO Swapping Cities (APIO20_swap) C++17
7 / 100
 583 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{
    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) {
        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) {
        int x = a, y = b;
        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[x].pb({y, w});
        ed[y].pb({x, 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 348 KB Output is correct
2 Correct 0 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 864 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 181 ms 42636 KB Output is correct
10 Correct 230 ms 51916 KB Output is correct
11 Correct 258 ms 51544 KB Output is correct
12 Correct 263 ms 54332 KB Output is correct
13 Runtime error 583 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 232 ms 45408 KB Output is correct
4 Correct 226 ms 47532 KB Output is correct
5 Correct 224 ms 46332 KB Output is correct
6 Correct 229 ms 47868 KB Output is correct
7 Correct 242 ms 47204 KB Output is correct
8 Correct 216 ms 45084 KB Output is correct
9 Correct 223 ms 46564 KB Output is correct
10 Correct 220 ms 44212 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 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 864 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 1 ms 860 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Incorrect 1 ms 860 KB Output isn't correct
15 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 348 KB Output is correct
3 Correct 0 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 864 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 181 ms 42636 KB Output is correct
11 Correct 230 ms 51916 KB Output is correct
12 Correct 258 ms 51544 KB Output is correct
13 Correct 263 ms 54332 KB Output is correct
14 Runtime error 583 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 348 KB Output is correct
2 Correct 0 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 864 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 181 ms 42636 KB Output is correct
10 Correct 230 ms 51916 KB Output is correct
11 Correct 258 ms 51544 KB Output is correct
12 Correct 263 ms 54332 KB Output is correct
13 Runtime error 583 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 348 KB Output is correct
3 Correct 0 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 864 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 181 ms 42636 KB Output is correct
11 Correct 230 ms 51916 KB Output is correct
12 Correct 258 ms 51544 KB Output is correct
13 Correct 263 ms 54332 KB Output is correct
14 Runtime error 583 ms 524288 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -