oj.uz

Submission #295687

# Submission time Handle Problem Language Result Execution time Memory
295687 2020-09-09T20:08:38 Z jhnah917 Swapping Cities (APIO20_swap) C++14
13 / 100
 481 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), (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 12 ms 13056 KB Output is correct
6 Correct 9 ms 13056 KB Output is correct
7 Correct 13 ms 13056 KB Output is correct
8 Correct 12 ms 13056 KB Output is correct
9 Correct 223 ms 40952 KB Output is correct
10 Correct 288 ms 49048 KB Output is correct
11 Correct 282 ms 47736 KB Output is correct
12 Correct 313 ms 50300 KB Output is correct
13 Correct 242 ms 52472 KB Output is correct
14 Correct 221 ms 40056 KB Output is correct
15 Correct 364 ms 50692 KB Output is correct
16 Correct 353 ms 47528 KB Output is correct
17 Correct 380 ms 54496 KB Output is correct
18 Correct 329 ms 52228 KB Output is correct
19 Correct 148 ms 22536 KB Output is correct
20 Correct 457 ms 50936 KB Output is correct
21 Correct 449 ms 48660 KB Output is correct
22 Correct 481 ms 52792 KB Output is correct
23 Correct 413 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 261 ms 38852 KB Output is correct
4 Correct 236 ms 39880 KB Output is correct
5 Correct 255 ms 39420 KB Output is correct
6 Correct 250 ms 39752 KB Output is correct
7 Correct 257 ms 39648 KB Output is correct
8 Correct 236 ms 38708 KB Output is correct
9 Correct 238 ms 39520 KB Output is correct
10 Correct 235 ms 38556 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 12 ms 13056 KB Output is correct
7 Correct 9 ms 13056 KB Output is correct
8 Correct 13 ms 13056 KB Output is correct
9 Correct 12 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 12 ms 13056 KB Output is correct
7 Correct 9 ms 13056 KB Output is correct
8 Correct 13 ms 13056 KB Output is correct
9 Correct 12 ms 13056 KB Output is correct
10 Correct 223 ms 40952 KB Output is correct
11 Correct 288 ms 49048 KB Output is correct
12 Correct 282 ms 47736 KB Output is correct
13 Correct 313 ms 50300 KB Output is correct
14 Correct 242 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 12 ms 13056 KB Output is correct
6 Correct 9 ms 13056 KB Output is correct
7 Correct 13 ms 13056 KB Output is correct
8 Correct 12 ms 13056 KB Output is correct
9 Correct 223 ms 40952 KB Output is correct
10 Correct 288 ms 49048 KB Output is correct
11 Correct 282 ms 47736 KB Output is correct
12 Correct 313 ms 50300 KB Output is correct
13 Correct 242 ms 52472 KB Output is correct
14 Correct 221 ms 40056 KB Output is correct
15 Correct 364 ms 50692 KB Output is correct
16 Correct 353 ms 47528 KB Output is correct
17 Correct 380 ms 54496 KB Output is correct
18 Correct 329 ms 52228 KB Output is correct
19 Correct 261 ms 38852 KB Output is correct
20 Correct 236 ms 39880 KB Output is correct
21 Correct 255 ms 39420 KB Output is correct
22 Correct 250 ms 39752 KB Output is correct
23 Correct 257 ms 39648 KB Output is correct
24 Correct 236 ms 38708 KB Output is correct
25 Correct 238 ms 39520 KB Output is correct
26 Correct 235 ms 38556 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 12 ms 13056 KB Output is correct
7 Correct 9 ms 13056 KB Output is correct
8 Correct 13 ms 13056 KB Output is correct
9 Correct 12 ms 13056 KB Output is correct
10 Correct 223 ms 40952 KB Output is correct
11 Correct 288 ms 49048 KB Output is correct
12 Correct 282 ms 47736 KB Output is correct
13 Correct 313 ms 50300 KB Output is correct
14 Correct 242 ms 52472 KB Output is correct
15 Correct 221 ms 40056 KB Output is correct
16 Correct 364 ms 50692 KB Output is correct
17 Correct 353 ms 47528 KB Output is correct
18 Correct 380 ms 54496 KB Output is correct
19 Correct 329 ms 52228 KB Output is correct
20 Correct 261 ms 38852 KB Output is correct
21 Correct 236 ms 39880 KB Output is correct
22 Correct 255 ms 39420 KB Output is correct
23 Correct 250 ms 39752 KB Output is correct
24 Correct 257 ms 39648 KB Output is correct
25 Correct 236 ms 38708 KB Output is correct
26 Correct 238 ms 39520 KB Output is correct
27 Correct 235 ms 38556 KB Output is correct
28 Incorrect 10 ms 12928 KB Output isn't correct
29 Halted 0 ms 0 KB -