oj.uz

Submission #295681

# Submission time Handle Problem Language Result Execution time Memory
295681 2020-09-09T20:01:31 Z jhnah917 Swapping Cities (APIO20_swap) C++14
13 / 100
 496 ms 58976 KB 
#include "swap.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

struct Edge{
    int s, e, x;
    bool operator < (const Edge &t) const {
        return tie(x, s, e) < tie(t.x, t.s, t.e);
    }
};

int par[101010];
int find(int v){ return v == par[v] ? v : par[v] = find(par[v]); }
int merge(int u, int v){
    u = find(u); v = find(v);
    if(u == v) return 0;
    par[u] = v; return 1;
}

const int sz = 1 << 17;
struct Seg{
    int tree[1 << 18];
    void update(int x, int v){
        x |= sz; tree[x] = v;
        while(x >>= 1) tree[x] = max(tree[x << 1], tree[x << 1 | 1]);
    }
    int query(int l, int r){
        l |= sz; r |= sz; int ret = 0;
        while(l <= r){
            if(l & 1) ret = max(ret, tree[l++]);
            if(~r & 1) ret = max(ret, tree[r--]);
            l >>= 1; r >>= 1;
        }
        return ret;
    }
};

struct HLD{
    vector<p> inp[101010];
    vector<int> g[101010];
    int w[101010], pv;
    int in[101010], top[101010], dep[101010], sz[101010], par[101010];
    Seg seg;
    void dfs(int v, int b){
        for(auto i : inp[v]) if(i.x != b) {
            g[v].push_back(i.x); w[i.x] = i.y;
            dep[i.x] = dep[v] + 1; par[i.x] = v;
            dfs(i.x, v);
        }
    }
    void dfs1(int v){
        sz[v] = 1;
        for(auto &i : g[v]){
            dfs1(i); sz[v] += sz[i];
            if(sz[i] > sz[g[v][0]]) swap(i, g[v][0]);
        }
    }
    void dfs2(int v){
        in[v] = ++pv;
        for(auto i : g[v]){
            top[i] = i == g[v][0] ? top[v] : i;
            dfs2(i);
        }
    }
    void init(int n){
        dfs(0, -1); dfs1(0); dfs2(0);
        for(int i=0; i<n; i++) seg.update(in[i], w[i]);
    }
    int query(int u, int v){
        int ret = 0;
        for(; top[u] != top[v]; u=par[top[u]]){
            if(dep[top[u]] < dep[top[v]]) swap(u, v);
            ret = max(ret, seg.query(in[top[u]], in[u]));
        }
        if(dep[u] > dep[v]) swap(u, v);
        ret = max(ret, seg.query(in[u]+1, in[v]));
        return ret;
    }
    void addEdge(int s, int e, int x){
        inp[s].emplace_back(e, x);
        inp[e].emplace_back(s, x);
    }
} t1, t2;

int n, m, deg[101010];
vector<Edge> edge;
vector<int> g[101010];
int deg_chk[101010], edge_cnt[101010];

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    n = N; m = M; edge.resize(m);
    for(int i=0; i<m; i++){
        edge[i].s = U[i]; edge[i].e = V[i]; edge[i].x = W[i];
        g[edge[i].s].push_back(edge[i].e);
        g[edge[i].e].push_back(edge[i].s);
    }
    sort(all(edge)); iota(par, par+101010, 0);
    for(auto i : edge){
        if(merge(i.s, i.e)) t1.addEdge(i.s, i.e, i.x), t2.addEdge(i.s, i.e, i.x);
        else{
            if(merge(i.s, n)) t2.addEdge(i.s, n, i.x);
            if(merge(i.e, n)) t2.addEdge(i.e, n, i.x);
        }
        if(++deg[i.s] == 3 && merge(i.s, n)) t2.addEdge(i.s, n, i.x);
        if(++deg[i.e] == 3 && merge(i.e, n)) t2.addEdge(i.e, n, i.x);
    }
    for(auto i : edge) edge_cnt[find(i.s)]++;
    for(int i=0; i<n; i++) if(deg[i] >= 3) deg_chk[find(i)] = 1;
    t1.init(n); t2.init(n+1);
}

int getMinimumFuelCapacity(int a, int b) {
    if(!deg_chk[find(a)] && m < n) return -1;
    return max(t1.query(a, b), min(t2.query(a, n), t2.query(b, n)));
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12672 KB Output is correct
2 Correct 9 ms 12672 KB Output is correct
3 Correct 9 ms 12672 KB Output is correct
4 Correct 9 ms 12800 KB Output is correct
5 Correct 10 ms 13056 KB Output is correct
6 Correct 10 ms 13056 KB Output is correct
7 Correct 10 ms 13056 KB Output is correct
8 Correct 10 ms 13056 KB Output is correct
9 Correct 222 ms 42616 KB Output is correct
10 Correct 284 ms 51120 KB Output is correct
11 Correct 281 ms 49784 KB Output is correct
12 Correct 297 ms 52344 KB Output is correct
13 Correct 235 ms 54560 KB Output is correct
14 Correct 220 ms 41976 KB Output is correct
15 Correct 373 ms 55196 KB Output is correct
16 Correct 364 ms 51880 KB Output is correct
17 Correct 382 ms 58976 KB Output is correct
18 Correct 324 ms 56692 KB Output is correct
19 Correct 159 ms 24440 KB Output is correct
20 Correct 463 ms 55160 KB Output is correct
21 Correct 480 ms 52920 KB Output is correct
22 Correct 496 ms 57196 KB Output is correct
23 Correct 428 ms 57440 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12672 KB Output is correct
2 Correct 9 ms 12672 KB Output is correct
3 Correct 251 ms 43396 KB Output is correct
4 Correct 258 ms 44488 KB Output is correct
5 Correct 265 ms 44280 KB Output is correct
6 Correct 263 ms 45000 KB Output is correct
7 Correct 259 ms 44520 KB Output is correct
8 Correct 249 ms 43152 KB Output is correct
9 Correct 258 ms 44304 KB Output is correct
10 Correct 252 ms 43424 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12672 KB Output is correct
2 Correct 9 ms 12672 KB Output is correct
3 Correct 9 ms 12672 KB Output is correct
4 Correct 9 ms 12672 KB Output is correct
5 Correct 9 ms 12800 KB Output is correct
6 Correct 10 ms 13056 KB Output is correct
7 Correct 10 ms 13056 KB Output is correct
8 Correct 10 ms 13056 KB Output is correct
9 Correct 10 ms 13056 KB Output is correct
10 Incorrect 10 ms 12928 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12672 KB Output is correct
2 Correct 9 ms 12672 KB Output is correct
3 Correct 9 ms 12672 KB Output is correct
4 Correct 9 ms 12672 KB Output is correct
5 Correct 9 ms 12800 KB Output is correct
6 Correct 10 ms 13056 KB Output is correct
7 Correct 10 ms 13056 KB Output is correct
8 Correct 10 ms 13056 KB Output is correct
9 Correct 10 ms 13056 KB Output is correct
10 Correct 222 ms 42616 KB Output is correct
11 Correct 284 ms 51120 KB Output is correct
12 Correct 281 ms 49784 KB Output is correct
13 Correct 297 ms 52344 KB Output is correct
14 Correct 235 ms 54560 KB Output is correct
15 Incorrect 10 ms 12928 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12672 KB Output is correct
2 Correct 9 ms 12672 KB Output is correct
3 Correct 9 ms 12672 KB Output is correct
4 Correct 9 ms 12800 KB Output is correct
5 Correct 10 ms 13056 KB Output is correct
6 Correct 10 ms 13056 KB Output is correct
7 Correct 10 ms 13056 KB Output is correct
8 Correct 10 ms 13056 KB Output is correct
9 Correct 222 ms 42616 KB Output is correct
10 Correct 284 ms 51120 KB Output is correct
11 Correct 281 ms 49784 KB Output is correct
12 Correct 297 ms 52344 KB Output is correct
13 Correct 235 ms 54560 KB Output is correct
14 Correct 220 ms 41976 KB Output is correct
15 Correct 373 ms 55196 KB Output is correct
16 Correct 364 ms 51880 KB Output is correct
17 Correct 382 ms 58976 KB Output is correct
18 Correct 324 ms 56692 KB Output is correct
19 Correct 251 ms 43396 KB Output is correct
20 Correct 258 ms 44488 KB Output is correct
21 Correct 265 ms 44280 KB Output is correct
22 Correct 263 ms 45000 KB Output is correct
23 Correct 259 ms 44520 KB Output is correct
24 Correct 249 ms 43152 KB Output is correct
25 Correct 258 ms 44304 KB Output is correct
26 Correct 252 ms 43424 KB Output is correct
27 Incorrect 10 ms 12928 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12672 KB Output is correct
2 Correct 9 ms 12672 KB Output is correct
3 Correct 9 ms 12672 KB Output is correct
4 Correct 9 ms 12672 KB Output is correct
5 Correct 9 ms 12800 KB Output is correct
6 Correct 10 ms 13056 KB Output is correct
7 Correct 10 ms 13056 KB Output is correct
8 Correct 10 ms 13056 KB Output is correct
9 Correct 10 ms 13056 KB Output is correct
10 Correct 222 ms 42616 KB Output is correct
11 Correct 284 ms 51120 KB Output is correct
12 Correct 281 ms 49784 KB Output is correct
13 Correct 297 ms 52344 KB Output is correct
14 Correct 235 ms 54560 KB Output is correct
15 Correct 220 ms 41976 KB Output is correct
16 Correct 373 ms 55196 KB Output is correct
17 Correct 364 ms 51880 KB Output is correct
18 Correct 382 ms 58976 KB Output is correct
19 Correct 324 ms 56692 KB Output is correct
20 Correct 251 ms 43396 KB Output is correct
21 Correct 258 ms 44488 KB Output is correct
22 Correct 265 ms 44280 KB Output is correct
23 Correct 263 ms 45000 KB Output is correct
24 Correct 259 ms 44520 KB Output is correct
25 Correct 249 ms 43152 KB Output is correct
26 Correct 258 ms 44304 KB Output is correct
27 Correct 252 ms 43424 KB Output is correct
28 Incorrect 10 ms 12928 KB Output isn't correct
29 Halted 0 ms 0 KB -