oj.uz

Submission #295727

# Submission time Handle Problem Language Result Execution time Memory
295727 2020-09-09T20:44:10 Z jhnah917 Swapping Cities (APIO20_swap) C++14
100 / 100
 607 ms 58336 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], flag;
vector<Edge> edge;
vector<int> g[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);
    iota(par, par+101010, 0);
    for(auto i : edge){
        if(merge(i.s, i.e)) 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), flag = 1;
        if(++deg[i.e] == 3 && merge(i.e, n)) t2.addEdge(i.e, n, i.x), flag = 1;
    }
    if(n <= m) flag = 1;
    t1.init(n); t2.init(n+1);
}

int getMinimumFuelCapacity(int a, int b){
    if(!flag) return -1;
    return max({t1.query(a, b), t2.query(a, b), 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 10 ms 12928 KB Output is correct
5 Correct 11 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 212 ms 42744 KB Output is correct
10 Correct 281 ms 51292 KB Output is correct
11 Correct 286 ms 49864 KB Output is correct
12 Correct 295 ms 52512 KB Output is correct
13 Correct 247 ms 54560 KB Output is correct
14 Correct 224 ms 42232 KB Output is correct
15 Correct 358 ms 54532 KB Output is correct
16 Correct 360 ms 51384 KB Output is correct
17 Correct 378 ms 58336 KB Output is correct
18 Correct 295 ms 56032 KB Output is correct
19 Correct 177 ms 24440 KB Output is correct
20 Correct 460 ms 54904 KB Output is correct
21 Correct 478 ms 52652 KB Output is correct
22 Correct 516 ms 56548 KB Output is correct
23 Correct 438 ms 56812 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 226 ms 42696 KB Output is correct
4 Correct 244 ms 43728 KB Output is correct
5 Correct 229 ms 43136 KB Output is correct
6 Correct 241 ms 43584 KB Output is correct
7 Correct 237 ms 43368 KB Output is correct
8 Correct 224 ms 42392 KB Output is correct
9 Correct 239 ms 43240 KB Output is correct
10 Correct 227 ms 42304 KB Output is correct

Subtask #3
17.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 10 ms 12928 KB Output is correct
6 Correct 11 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 10 ms 12960 KB Output is correct
11 Correct 10 ms 13056 KB Output is correct
12 Correct 10 ms 13056 KB Output is correct
13 Correct 10 ms 12928 KB Output is correct
14 Correct 10 ms 12928 KB Output is correct
15 Correct 10 ms 13056 KB Output is correct
16 Correct 10 ms 13056 KB Output is correct
17 Correct 11 ms 13056 KB Output is correct
18 Correct 10 ms 13184 KB Output is correct
19 Correct 10 ms 12928 KB Output is correct
20 Correct 10 ms 13056 KB Output is correct
21 Correct 11 ms 12928 KB Output is correct
22 Correct 10 ms 12928 KB Output is correct
23 Correct 10 ms 12928 KB Output is correct
24 Correct 11 ms 13056 KB Output is correct
25 Correct 11 ms 13056 KB Output is correct
26 Correct 11 ms 13056 KB Output is correct
27 Correct 10 ms 13056 KB Output is correct
28 Correct 11 ms 13056 KB Output is correct

Subtask #4
20.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 10 ms 12928 KB Output is correct
6 Correct 11 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 212 ms 42744 KB Output is correct
11 Correct 281 ms 51292 KB Output is correct
12 Correct 286 ms 49864 KB Output is correct
13 Correct 295 ms 52512 KB Output is correct
14 Correct 247 ms 54560 KB Output is correct
15 Correct 10 ms 12960 KB Output is correct
16 Correct 10 ms 13056 KB Output is correct
17 Correct 10 ms 13056 KB Output is correct
18 Correct 10 ms 12928 KB Output is correct
19 Correct 10 ms 12928 KB Output is correct
20 Correct 10 ms 13056 KB Output is correct
21 Correct 10 ms 13056 KB Output is correct
22 Correct 11 ms 13056 KB Output is correct
23 Correct 10 ms 13184 KB Output is correct
24 Correct 31 ms 16768 KB Output is correct
25 Correct 274 ms 51576 KB Output is correct
26 Correct 247 ms 47992 KB Output is correct
27 Correct 238 ms 45176 KB Output is correct
28 Correct 245 ms 44152 KB Output is correct
29 Correct 250 ms 43132 KB Output is correct
30 Correct 222 ms 39816 KB Output is correct
31 Correct 270 ms 50936 KB Output is correct
32 Correct 268 ms 50552 KB Output is correct
33 Correct 215 ms 51960 KB Output is correct
34 Correct 239 ms 42232 KB Output is correct
35 Correct 10 ms 12928 KB Output is correct
36 Correct 10 ms 13056 KB Output is correct
37 Correct 11 ms 12928 KB Output is correct
38 Correct 10 ms 12928 KB Output is correct
39 Correct 10 ms 12928 KB Output is correct
40 Correct 11 ms 13056 KB Output is correct
41 Correct 11 ms 13056 KB Output is correct
42 Correct 11 ms 13056 KB Output is correct
43 Correct 10 ms 13056 KB Output is correct
44 Correct 11 ms 13056 KB Output is correct
45 Correct 263 ms 39952 KB Output is correct
46 Correct 249 ms 46460 KB Output is correct
47 Correct 254 ms 44028 KB Output is correct
48 Correct 251 ms 42872 KB Output is correct
49 Correct 98 ms 23544 KB Output is correct
50 Correct 100 ms 22268 KB Output is correct
51 Correct 203 ms 35448 KB Output is correct
52 Correct 332 ms 50356 KB Output is correct
53 Correct 298 ms 47212 KB Output is correct
54 Correct 364 ms 55032 KB Output is correct
55 Correct 212 ms 53752 KB Output is correct
56 Correct 323 ms 46456 KB Output is correct

Subtask #5
23.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 10 ms 12928 KB Output is correct
5 Correct 11 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 212 ms 42744 KB Output is correct
10 Correct 281 ms 51292 KB Output is correct
11 Correct 286 ms 49864 KB Output is correct
12 Correct 295 ms 52512 KB Output is correct
13 Correct 247 ms 54560 KB Output is correct
14 Correct 224 ms 42232 KB Output is correct
15 Correct 358 ms 54532 KB Output is correct
16 Correct 360 ms 51384 KB Output is correct
17 Correct 378 ms 58336 KB Output is correct
18 Correct 295 ms 56032 KB Output is correct
19 Correct 226 ms 42696 KB Output is correct
20 Correct 244 ms 43728 KB Output is correct
21 Correct 229 ms 43136 KB Output is correct
22 Correct 241 ms 43584 KB Output is correct
23 Correct 237 ms 43368 KB Output is correct
24 Correct 224 ms 42392 KB Output is correct
25 Correct 239 ms 43240 KB Output is correct
26 Correct 227 ms 42304 KB Output is correct
27 Correct 10 ms 12960 KB Output is correct
28 Correct 10 ms 13056 KB Output is correct
29 Correct 10 ms 13056 KB Output is correct
30 Correct 10 ms 12928 KB Output is correct
31 Correct 10 ms 12928 KB Output is correct
32 Correct 10 ms 13056 KB Output is correct
33 Correct 10 ms 13056 KB Output is correct
34 Correct 11 ms 13056 KB Output is correct
35 Correct 10 ms 13184 KB Output is correct
36 Correct 31 ms 16768 KB Output is correct
37 Correct 274 ms 51576 KB Output is correct
38 Correct 247 ms 47992 KB Output is correct
39 Correct 238 ms 45176 KB Output is correct
40 Correct 245 ms 44152 KB Output is correct
41 Correct 250 ms 43132 KB Output is correct
42 Correct 222 ms 39816 KB Output is correct
43 Correct 270 ms 50936 KB Output is correct
44 Correct 268 ms 50552 KB Output is correct
45 Correct 215 ms 51960 KB Output is correct
46 Correct 239 ms 42232 KB Output is correct
47 Correct 46 ms 16876 KB Output is correct
48 Correct 516 ms 53984 KB Output is correct
49 Correct 515 ms 51680 KB Output is correct
50 Correct 507 ms 50236 KB Output is correct
51 Correct 503 ms 49388 KB Output is correct
52 Correct 472 ms 46632 KB Output is correct
53 Correct 374 ms 38124 KB Output is correct
54 Correct 533 ms 53604 KB Output is correct
55 Correct 523 ms 54496 KB Output is correct
56 Correct 427 ms 57824 KB Output is correct
57 Correct 488 ms 47712 KB Output is correct

Subtask #6
27.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 10 ms 12928 KB Output is correct
6 Correct 11 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 212 ms 42744 KB Output is correct
11 Correct 281 ms 51292 KB Output is correct
12 Correct 286 ms 49864 KB Output is correct
13 Correct 295 ms 52512 KB Output is correct
14 Correct 247 ms 54560 KB Output is correct
15 Correct 224 ms 42232 KB Output is correct
16 Correct 358 ms 54532 KB Output is correct
17 Correct 360 ms 51384 KB Output is correct
18 Correct 378 ms 58336 KB Output is correct
19 Correct 295 ms 56032 KB Output is correct
20 Correct 226 ms 42696 KB Output is correct
21 Correct 244 ms 43728 KB Output is correct
22 Correct 229 ms 43136 KB Output is correct
23 Correct 241 ms 43584 KB Output is correct
24 Correct 237 ms 43368 KB Output is correct
25 Correct 224 ms 42392 KB Output is correct
26 Correct 239 ms 43240 KB Output is correct
27 Correct 227 ms 42304 KB Output is correct
28 Correct 10 ms 12960 KB Output is correct
29 Correct 10 ms 13056 KB Output is correct
30 Correct 10 ms 13056 KB Output is correct
31 Correct 10 ms 12928 KB Output is correct
32 Correct 10 ms 12928 KB Output is correct
33 Correct 10 ms 13056 KB Output is correct
34 Correct 10 ms 13056 KB Output is correct
35 Correct 11 ms 13056 KB Output is correct
36 Correct 10 ms 13184 KB Output is correct
37 Correct 31 ms 16768 KB Output is correct
38 Correct 274 ms 51576 KB Output is correct
39 Correct 247 ms 47992 KB Output is correct
40 Correct 238 ms 45176 KB Output is correct
41 Correct 245 ms 44152 KB Output is correct
42 Correct 250 ms 43132 KB Output is correct
43 Correct 222 ms 39816 KB Output is correct
44 Correct 270 ms 50936 KB Output is correct
45 Correct 268 ms 50552 KB Output is correct
46 Correct 215 ms 51960 KB Output is correct
47 Correct 239 ms 42232 KB Output is correct
48 Correct 46 ms 16876 KB Output is correct
49 Correct 516 ms 53984 KB Output is correct
50 Correct 515 ms 51680 KB Output is correct
51 Correct 507 ms 50236 KB Output is correct
52 Correct 503 ms 49388 KB Output is correct
53 Correct 472 ms 46632 KB Output is correct
54 Correct 374 ms 38124 KB Output is correct
55 Correct 533 ms 53604 KB Output is correct
56 Correct 523 ms 54496 KB Output is correct
57 Correct 427 ms 57824 KB Output is correct
58 Correct 488 ms 47712 KB Output is correct
59 Correct 177 ms 24440 KB Output is correct
60 Correct 460 ms 54904 KB Output is correct
61 Correct 478 ms 52652 KB Output is correct
62 Correct 516 ms 56548 KB Output is correct
63 Correct 438 ms 56812 KB Output is correct
64 Correct 10 ms 12928 KB Output is correct
65 Correct 10 ms 13056 KB Output is correct
66 Correct 11 ms 12928 KB Output is correct
67 Correct 10 ms 12928 KB Output is correct
68 Correct 10 ms 12928 KB Output is correct
69 Correct 11 ms 13056 KB Output is correct
70 Correct 11 ms 13056 KB Output is correct
71 Correct 11 ms 13056 KB Output is correct
72 Correct 10 ms 13056 KB Output is correct
73 Correct 11 ms 13056 KB Output is correct
74 Correct 263 ms 39952 KB Output is correct
75 Correct 249 ms 46460 KB Output is correct
76 Correct 254 ms 44028 KB Output is correct
77 Correct 251 ms 42872 KB Output is correct
78 Correct 98 ms 23544 KB Output is correct
79 Correct 100 ms 22268 KB Output is correct
80 Correct 203 ms 35448 KB Output is correct
81 Correct 332 ms 50356 KB Output is correct
82 Correct 298 ms 47212 KB Output is correct
83 Correct 364 ms 55032 KB Output is correct
84 Correct 212 ms 53752 KB Output is correct
85 Correct 323 ms 46456 KB Output is correct
86 Correct 133 ms 24140 KB Output is correct
87 Correct 514 ms 51144 KB Output is correct
88 Correct 514 ms 51300 KB Output is correct
89 Correct 407 ms 45592 KB Output is correct
90 Correct 256 ms 27732 KB Output is correct
91 Correct 298 ms 29388 KB Output is correct
92 Correct 421 ms 40408 KB Output is correct
93 Correct 552 ms 55480 KB Output is correct
94 Correct 515 ms 51412 KB Output is correct
95 Correct 607 ms 57848 KB Output is correct
96 Correct 432 ms 54880 KB Output is correct
97 Correct 518 ms 49344 KB Output is correct