oj.uz

Submission #558763

# Submission time Handle Problem Language Result Execution time Memory
558763 2022-05-08T09:33:59 Z Ai7081 Swapping Cities (APIO20_swap) C++17
6 / 100
 533 ms 43052 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const bool debug = 1;

const int N = 1e5 + 5;
const int L = 20;
const int inf = 2e9;

struct edge{
    int u, v, w;
    bool operator < (const edge &o) const {return w<o.w;}
};

int n, m;
int p[N][L], ma[N][L], tin[N], tout[N];
int sz[N], dep[N], id[N], top[N], timer;
int root[N];
int t[4*N];
vector<pair<int, int>> adj[N];
vector<edge> back_edge, all_edge;

int findroot(int x) {return root[x]==x?x:root[x]=findroot(root[x]);}

int dfs(int v=0) {
    sz[v] = 1;
    tin[v] = ++timer;
    for (int i=1; i<L; i++) {
        p[v][i] = p[p[v][i-1]][i-1];
        ma[v][i] = max(ma[v][i-1], ma[p[v][i-1]][i-1]);
    }
    for (auto [to, w] : adj[v]) if (to!=p[v][0]) {
        p[to][0] = v;
        ma[to][0] = w;
        dep[to] = dep[v] + 1;
        sz[v] += dfs(to);
    }
    tout[v] = ++timer;
    return sz[v];
}

bool is_anc(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int lca(int u, int v) {
    int ret = -1;
    for (int i=L-1; i>=0; i--) if (!is_anc(p[u][i], v)) {
        ret = max(ret, ma[u][i]); u = p[u][i];
    }
    for (int i=L-1; i>=0; i--) if (!is_anc(p[v][i], u)) {
        ret = max(ret, ma[v][i]); v = p[v][i];
    }
    if (!is_anc(u, v)) ret = max(ret, ma[u][0]);
    if (!is_anc(v, u)) ret = max(ret, ma[v][0]);
    return ret;
}

void hld(int v=0, int tp=0) {
    id[v] = ++timer;
    top[v] = tp;
    int h_chi = -1, h_sz = -1;
    for (auto [to, w] : adj[v]) if (to!=p[v][0] && h_sz<sz[to]) h_sz = sz[to], h_chi = to;
    if (h_chi == -1) return;
    hld(h_chi, tp);
    for (auto [to, w] : adj[v]) if(to!=p[v][0] && to!=h_chi) hld(to, to);
}

void upd_seg(int l, int r, int val, int v=1, int tl=1, int tr=n) {
    if (tl > r || tr < l) return;
    if (l <= tl && tr <= r) {
        if (t[v] == -1) t[v] = val;
        return;
    }
    int tm = (tl+tr)/2;
    upd_seg(l, r, val, 2*v, tl, tm);
    upd_seg(l, r, val, 2*v+1, tm+1, tr);
}

int query_seg(int l, int r, int v=1, int tl=1, int tr=n) {
    if (tl > r || tr < l) return -1;
    if (l <= tl && tr <= r) return t[v];
    int tm = (tl+tr)/2;
    return max(t[v], max(query_seg(l, r, 2*v, tl, tm), query_seg(l, r, 2*v+1, tm+1, tr)));
}

void upd_path(int u, int v, int val) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        upd_seg(id[top[u]], id[u], val);
        u = p[top[u]][0];
    }
    if (u != v) {
        if (dep[u] > dep[v]) swap(u, v);
        upd_seg(id[u]+1, id[v], val);
    }
}

int query_path(int u, int v) {
    int ret = -1;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        ret = max(ret, query_seg(id[top[u]], id[u]));
        u = p[top[u]][0];
    }
    if (u != v) {
        if (dep[u] > dep[v]) swap(u, v);
        ret =  max(ret, query_seg(id[u]+1, id[v]));
    }
    return ret;
}

void init(int NN, int MM, vector<int> U, vector<int> V, vector<int> W)
{
    n = NN, m = MM;
    for (int i=0; i<m; i++) all_edge.push_back({U[i], V[i], W[i]});
    sort(all_edge.begin(), all_edge.end());
    for (int i=0; i<n; i++) root[i] = i;
    for (auto [u, v, w] : all_edge) {
        int ru = findroot(u), rv = findroot(v);
        if (ru == rv) back_edge.push_back({u, v, w});
        else root[rv] = ru, adj[u].push_back({v, w}), adj[v].push_back({u, w});
    }
    dfs();
    timer = 0;
    hld();
    fill_n(t, 4*N, -1);
    for (auto [u, v, w] : back_edge) upd_path(u, v, w);
}

int getMinimumFuelCapacity(int X, int Y)
{
    int res = query_path(X, Y);
    if (res == -1) return -1;
    return max(res, lca(X, Y));
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4192 KB Output is correct
2 Correct 2 ms 4188 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 3 ms 4308 KB Output is correct
5 Correct 3 ms 4436 KB Output is correct
6 Correct 3 ms 4436 KB Output is correct
7 Correct 3 ms 4564 KB Output is correct
8 Correct 3 ms 4592 KB Output is correct
9 Correct 106 ms 29272 KB Output is correct
10 Correct 154 ms 36268 KB Output is correct
11 Correct 145 ms 35228 KB Output is correct
12 Correct 194 ms 37204 KB Output is correct
13 Correct 125 ms 38976 KB Output is correct
14 Correct 133 ms 28968 KB Output is correct
15 Correct 321 ms 40168 KB Output is correct
16 Correct 280 ms 37960 KB Output is correct
17 Correct 281 ms 43052 KB Output is correct
18 Correct 307 ms 41652 KB Output is correct
19 Correct 150 ms 14908 KB Output is correct
20 Correct 532 ms 40636 KB Output is correct
21 Correct 522 ms 39036 KB Output is correct
22 Correct 533 ms 42356 KB Output is correct
23 Correct 516 ms 42644 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4192 KB Output is correct
2 Correct 2 ms 4188 KB Output is correct
3 Incorrect 249 ms 34276 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4192 KB Output is correct
2 Correct 2 ms 4188 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 3 ms 4308 KB Output is correct
5 Correct 3 ms 4436 KB Output is correct
6 Correct 3 ms 4436 KB Output is correct
7 Correct 3 ms 4564 KB Output is correct
8 Correct 3 ms 4592 KB Output is correct
9 Correct 2 ms 4180 KB Output is correct
10 Incorrect 3 ms 4460 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 3 ms 4192 KB Output is correct
3 Correct 2 ms 4188 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 3 ms 4308 KB Output is correct
6 Correct 3 ms 4436 KB Output is correct
7 Correct 3 ms 4436 KB Output is correct
8 Correct 3 ms 4564 KB Output is correct
9 Correct 3 ms 4592 KB Output is correct
10 Correct 106 ms 29272 KB Output is correct
11 Correct 154 ms 36268 KB Output is correct
12 Correct 145 ms 35228 KB Output is correct
13 Correct 194 ms 37204 KB Output is correct
14 Correct 125 ms 38976 KB Output is correct
15 Incorrect 3 ms 4460 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4192 KB Output is correct
2 Correct 2 ms 4188 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 3 ms 4308 KB Output is correct
5 Correct 3 ms 4436 KB Output is correct
6 Correct 3 ms 4436 KB Output is correct
7 Correct 3 ms 4564 KB Output is correct
8 Correct 3 ms 4592 KB Output is correct
9 Correct 106 ms 29272 KB Output is correct
10 Correct 154 ms 36268 KB Output is correct
11 Correct 145 ms 35228 KB Output is correct
12 Correct 194 ms 37204 KB Output is correct
13 Correct 125 ms 38976 KB Output is correct
14 Correct 133 ms 28968 KB Output is correct
15 Correct 321 ms 40168 KB Output is correct
16 Correct 280 ms 37960 KB Output is correct
17 Correct 281 ms 43052 KB Output is correct
18 Correct 307 ms 41652 KB Output is correct
19 Incorrect 249 ms 34276 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 3 ms 4192 KB Output is correct
3 Correct 2 ms 4188 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 3 ms 4308 KB Output is correct
6 Correct 3 ms 4436 KB Output is correct
7 Correct 3 ms 4436 KB Output is correct
8 Correct 3 ms 4564 KB Output is correct
9 Correct 3 ms 4592 KB Output is correct
10 Correct 106 ms 29272 KB Output is correct
11 Correct 154 ms 36268 KB Output is correct
12 Correct 145 ms 35228 KB Output is correct
13 Correct 194 ms 37204 KB Output is correct
14 Correct 125 ms 38976 KB Output is correct
15 Correct 133 ms 28968 KB Output is correct
16 Correct 321 ms 40168 KB Output is correct
17 Correct 280 ms 37960 KB Output is correct
18 Correct 281 ms 43052 KB Output is correct
19 Correct 307 ms 41652 KB Output is correct
20 Incorrect 249 ms 34276 KB Output isn't correct
21 Halted 0 ms 0 KB -