oj.uz

Submission #295689

# Submission time Handle Problem Language Result Execution time Memory
295689 2020-09-09T20:09:20 Z jhnah917 Swapping Cities (APIO20_swap) C++14
13 / 100
 460 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 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 11 ms 13056 KB Output is correct
8 Correct 10 ms 13056 KB Output is correct
9 Correct 208 ms 40952 KB Output is correct
10 Correct 269 ms 49016 KB Output is correct
11 Correct 261 ms 47864 KB Output is correct
12 Correct 279 ms 50296 KB Output is correct
13 Correct 249 ms 52472 KB Output is correct
14 Correct 213 ms 40056 KB Output is correct
15 Correct 360 ms 50692 KB Output is correct
16 Correct 329 ms 47532 KB Output is correct
17 Correct 373 ms 54496 KB Output is correct
18 Correct 293 ms 52192 KB Output is correct
19 Correct 148 ms 22520 KB Output is correct
20 Correct 439 ms 51064 KB Output is correct
21 Correct 433 ms 48692 KB Output is correct
22 Correct 460 ms 52864 KB Output is correct
23 Correct 406 ms 53220 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 230 ms 38896 KB Output is correct
4 Correct 235 ms 40008 KB Output is correct
5 Correct 237 ms 39672 KB Output is correct
6 Correct 239 ms 39756 KB Output is correct
7 Correct 242 ms 39732 KB Output is correct
8 Correct 228 ms 38672 KB Output is correct
9 Correct 229 ms 39520 KB Output is correct
10 Correct 225 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 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 11 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 11 ms 13056 KB Output is correct
9 Correct 10 ms 13056 KB Output is correct
10 Correct 208 ms 40952 KB Output is correct
11 Correct 269 ms 49016 KB Output is correct
12 Correct 261 ms 47864 KB Output is correct
13 Correct 279 ms 50296 KB Output is correct
14 Correct 249 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 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 11 ms 13056 KB Output is correct
8 Correct 10 ms 13056 KB Output is correct
9 Correct 208 ms 40952 KB Output is correct
10 Correct 269 ms 49016 KB Output is correct
11 Correct 261 ms 47864 KB Output is correct
12 Correct 279 ms 50296 KB Output is correct
13 Correct 249 ms 52472 KB Output is correct
14 Correct 213 ms 40056 KB Output is correct
15 Correct 360 ms 50692 KB Output is correct
16 Correct 329 ms 47532 KB Output is correct
17 Correct 373 ms 54496 KB Output is correct
18 Correct 293 ms 52192 KB Output is correct
19 Correct 230 ms 38896 KB Output is correct
20 Correct 235 ms 40008 KB Output is correct
21 Correct 237 ms 39672 KB Output is correct
22 Correct 239 ms 39756 KB Output is correct
23 Correct 242 ms 39732 KB Output is correct
24 Correct 228 ms 38672 KB Output is correct
25 Correct 229 ms 39520 KB Output is correct
26 Correct 225 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 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 11 ms 13056 KB Output is correct
9 Correct 10 ms 13056 KB Output is correct
10 Correct 208 ms 40952 KB Output is correct
11 Correct 269 ms 49016 KB Output is correct
12 Correct 261 ms 47864 KB Output is correct
13 Correct 279 ms 50296 KB Output is correct
14 Correct 249 ms 52472 KB Output is correct
15 Correct 213 ms 40056 KB Output is correct
16 Correct 360 ms 50692 KB Output is correct
17 Correct 329 ms 47532 KB Output is correct
18 Correct 373 ms 54496 KB Output is correct
19 Correct 293 ms 52192 KB Output is correct
20 Correct 230 ms 38896 KB Output is correct
21 Correct 235 ms 40008 KB Output is correct
22 Correct 237 ms 39672 KB Output is correct
23 Correct 239 ms 39756 KB Output is correct
24 Correct 242 ms 39732 KB Output is correct
25 Correct 228 ms 38672 KB Output is correct
26 Correct 229 ms 39520 KB Output is correct
27 Correct 225 ms 38556 KB Output is correct
28 Incorrect 10 ms 12928 KB Output isn't correct
29 Halted 0 ms 0 KB -