oj.uz

Submission #295696

# Submission time Handle Problem Language Result Execution time Memory
295696 2020-09-09T20:14:47 Z jhnah917 Swapping Cities (APIO20_swap) C++14
13 / 100
 591 ms 54752 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; assert(!tree[x]); 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, 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 12928 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 211 ms 41080 KB Output is correct
10 Correct 276 ms 49144 KB Output is correct
11 Correct 292 ms 47864 KB Output is correct
12 Correct 314 ms 50296 KB Output is correct
13 Correct 244 ms 52472 KB Output is correct
14 Correct 207 ms 40188 KB Output is correct
15 Correct 340 ms 50948 KB Output is correct
16 Correct 346 ms 47688 KB Output is correct
17 Correct 371 ms 54752 KB Output is correct
18 Correct 321 ms 52320 KB Output is correct
19 Correct 174 ms 22596 KB Output is correct
20 Correct 512 ms 51056 KB Output is correct
21 Correct 518 ms 48948 KB Output is correct
22 Correct 591 ms 52960 KB Output is correct
23 Correct 454 ms 53216 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 241 ms 39076 KB Output is correct
4 Correct 255 ms 39976 KB Output is correct
5 Correct 322 ms 39672 KB Output is correct
6 Correct 261 ms 40136 KB Output is correct
7 Correct 284 ms 40032 KB Output is correct
8 Correct 246 ms 39056 KB Output is correct
9 Correct 252 ms 39780 KB Output is correct
10 Correct 259 ms 38940 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 12928 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 12928 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 211 ms 41080 KB Output is correct
11 Correct 276 ms 49144 KB Output is correct
12 Correct 292 ms 47864 KB Output is correct
13 Correct 314 ms 50296 KB Output is correct
14 Correct 244 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 12928 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 211 ms 41080 KB Output is correct
10 Correct 276 ms 49144 KB Output is correct
11 Correct 292 ms 47864 KB Output is correct
12 Correct 314 ms 50296 KB Output is correct
13 Correct 244 ms 52472 KB Output is correct
14 Correct 207 ms 40188 KB Output is correct
15 Correct 340 ms 50948 KB Output is correct
16 Correct 346 ms 47688 KB Output is correct
17 Correct 371 ms 54752 KB Output is correct
18 Correct 321 ms 52320 KB Output is correct
19 Correct 241 ms 39076 KB Output is correct
20 Correct 255 ms 39976 KB Output is correct
21 Correct 322 ms 39672 KB Output is correct
22 Correct 261 ms 40136 KB Output is correct
23 Correct 284 ms 40032 KB Output is correct
24 Correct 246 ms 39056 KB Output is correct
25 Correct 252 ms 39780 KB Output is correct
26 Correct 259 ms 38940 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 12928 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 211 ms 41080 KB Output is correct
11 Correct 276 ms 49144 KB Output is correct
12 Correct 292 ms 47864 KB Output is correct
13 Correct 314 ms 50296 KB Output is correct
14 Correct 244 ms 52472 KB Output is correct
15 Correct 207 ms 40188 KB Output is correct
16 Correct 340 ms 50948 KB Output is correct
17 Correct 346 ms 47688 KB Output is correct
18 Correct 371 ms 54752 KB Output is correct
19 Correct 321 ms 52320 KB Output is correct
20 Correct 241 ms 39076 KB Output is correct
21 Correct 255 ms 39976 KB Output is correct
22 Correct 322 ms 39672 KB Output is correct
23 Correct 261 ms 40136 KB Output is correct
24 Correct 284 ms 40032 KB Output is correct
25 Correct 246 ms 39056 KB Output is correct
26 Correct 252 ms 39780 KB Output is correct
27 Correct 259 ms 38940 KB Output is correct
28 Incorrect 10 ms 12928 KB Output isn't correct
29 Halted 0 ms 0 KB -