oj.uz

Submission #295685

# Submission time Handle Problem Language Result Execution time Memory
295685 2020-09-09T20:04:22 Z jhnah917 Swapping Cities (APIO20_swap) C++14
13 / 100
 478 ms 54496 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), 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(int i=0; i<n; i++) if(deg[i] >= 3) 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), min(t2.query(a, n), t2.query(b, n)));
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12672 KB Output is correct
2 Correct 8 ms 12672 KB Output is correct
3 Correct 8 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 221 ms 40908 KB Output is correct
10 Correct 296 ms 49204 KB Output is correct
11 Correct 273 ms 47740 KB Output is correct
12 Correct 290 ms 50296 KB Output is correct
13 Correct 239 ms 52472 KB Output is correct
14 Correct 219 ms 40056 KB Output is correct
15 Correct 355 ms 50692 KB Output is correct
16 Correct 356 ms 47684 KB Output is correct
17 Correct 370 ms 54496 KB Output is correct
18 Correct 307 ms 52320 KB Output is correct
19 Correct 158 ms 22520 KB Output is correct
20 Correct 460 ms 51040 KB Output is correct
21 Correct 473 ms 48692 KB Output is correct
22 Correct 478 ms 52704 KB Output is correct
23 Correct 407 ms 53088 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12672 KB Output is correct
2 Correct 8 ms 12672 KB Output is correct
3 Correct 230 ms 38916 KB Output is correct
4 Correct 254 ms 39880 KB Output is correct
5 Correct 248 ms 39528 KB Output is correct
6 Correct 241 ms 39752 KB Output is correct
7 Correct 246 ms 39648 KB Output is correct
8 Correct 237 ms 38672 KB Output is correct
9 Correct 241 ms 39396 KB Output is correct
10 Correct 238 ms 38456 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 8 ms 12672 KB Output is correct
3 Correct 8 ms 12672 KB Output is correct
4 Correct 8 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 8 ms 12672 KB Output is correct
3 Correct 8 ms 12672 KB Output is correct
4 Correct 8 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 221 ms 40908 KB Output is correct
11 Correct 296 ms 49204 KB Output is correct
12 Correct 273 ms 47740 KB Output is correct
13 Correct 290 ms 50296 KB Output is correct
14 Correct 239 ms 52472 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 8 ms 12672 KB Output is correct
2 Correct 8 ms 12672 KB Output is correct
3 Correct 8 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 221 ms 40908 KB Output is correct
10 Correct 296 ms 49204 KB Output is correct
11 Correct 273 ms 47740 KB Output is correct
12 Correct 290 ms 50296 KB Output is correct
13 Correct 239 ms 52472 KB Output is correct
14 Correct 219 ms 40056 KB Output is correct
15 Correct 355 ms 50692 KB Output is correct
16 Correct 356 ms 47684 KB Output is correct
17 Correct 370 ms 54496 KB Output is correct
18 Correct 307 ms 52320 KB Output is correct
19 Correct 230 ms 38916 KB Output is correct
20 Correct 254 ms 39880 KB Output is correct
21 Correct 248 ms 39528 KB Output is correct
22 Correct 241 ms 39752 KB Output is correct
23 Correct 246 ms 39648 KB Output is correct
24 Correct 237 ms 38672 KB Output is correct
25 Correct 241 ms 39396 KB Output is correct
26 Correct 238 ms 38456 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 8 ms 12672 KB Output is correct
3 Correct 8 ms 12672 KB Output is correct
4 Correct 8 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 221 ms 40908 KB Output is correct
11 Correct 296 ms 49204 KB Output is correct
12 Correct 273 ms 47740 KB Output is correct
13 Correct 290 ms 50296 KB Output is correct
14 Correct 239 ms 52472 KB Output is correct
15 Correct 219 ms 40056 KB Output is correct
16 Correct 355 ms 50692 KB Output is correct
17 Correct 356 ms 47684 KB Output is correct
18 Correct 370 ms 54496 KB Output is correct
19 Correct 307 ms 52320 KB Output is correct
20 Correct 230 ms 38916 KB Output is correct
21 Correct 254 ms 39880 KB Output is correct
22 Correct 248 ms 39528 KB Output is correct
23 Correct 241 ms 39752 KB Output is correct
24 Correct 246 ms 39648 KB Output is correct
25 Correct 237 ms 38672 KB Output is correct
26 Correct 241 ms 39396 KB Output is correct
27 Correct 238 ms 38456 KB Output is correct
28 Incorrect 10 ms 12928 KB Output isn't correct
29 Halted 0 ms 0 KB -