oj.uz

답안 #295692

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
295692 2020-09-09T20:10:27 Z jhnah917 자매 도시 (APIO20_swap) C++14
13 / 100
 528 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, b), t2.query(a, n), t2.query(b, n)});
}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 12672 KB Output is correct
2 Correct 9 ms 12672 KB Output is correct
3 Correct 9 ms 12800 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 218 ms 40956 KB Output is correct
10 Correct 286 ms 49196 KB Output is correct
11 Correct 274 ms 47736 KB Output is correct
12 Correct 297 ms 50424 KB Output is correct
13 Correct 233 ms 52604 KB Output is correct
14 Correct 219 ms 40184 KB Output is correct
15 Correct 354 ms 50696 KB Output is correct
16 Correct 341 ms 47656 KB Output is correct
17 Correct 368 ms 54496 KB Output is correct
18 Correct 340 ms 52320 KB Output is correct
19 Correct 178 ms 22520 KB Output is correct
20 Correct 528 ms 51064 KB Output is correct
21 Correct 493 ms 48692 KB Output is correct
22 Correct 495 ms 52704 KB Output is correct
23 Correct 459 ms 53072 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 12672 KB Output is correct
2 Correct 9 ms 12672 KB Output is correct
3 Correct 245 ms 38860 KB Output is correct
4 Correct 241 ms 39880 KB Output is correct
5 Correct 248 ms 39544 KB Output is correct
6 Correct 250 ms 39756 KB Output is correct
7 Correct 260 ms 39652 KB Output is correct
8 Correct 239 ms 38788 KB Output is correct
9 Correct 243 ms 39516 KB Output is correct
10 Correct 239 ms 38556 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 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 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

# 결과 실행 시간 메모리 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 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 218 ms 40956 KB Output is correct
11 Correct 286 ms 49196 KB Output is correct
12 Correct 274 ms 47736 KB Output is correct
13 Correct 297 ms 50424 KB Output is correct
14 Correct 233 ms 52604 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

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 12672 KB Output is correct
2 Correct 9 ms 12672 KB Output is correct
3 Correct 9 ms 12800 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 218 ms 40956 KB Output is correct
10 Correct 286 ms 49196 KB Output is correct
11 Correct 274 ms 47736 KB Output is correct
12 Correct 297 ms 50424 KB Output is correct
13 Correct 233 ms 52604 KB Output is correct
14 Correct 219 ms 40184 KB Output is correct
15 Correct 354 ms 50696 KB Output is correct
16 Correct 341 ms 47656 KB Output is correct
17 Correct 368 ms 54496 KB Output is correct
18 Correct 340 ms 52320 KB Output is correct
19 Correct 245 ms 38860 KB Output is correct
20 Correct 241 ms 39880 KB Output is correct
21 Correct 248 ms 39544 KB Output is correct
22 Correct 250 ms 39756 KB Output is correct
23 Correct 260 ms 39652 KB Output is correct
24 Correct 239 ms 38788 KB Output is correct
25 Correct 243 ms 39516 KB Output is correct
26 Correct 239 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

# 결과 실행 시간 메모리 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 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 218 ms 40956 KB Output is correct
11 Correct 286 ms 49196 KB Output is correct
12 Correct 274 ms 47736 KB Output is correct
13 Correct 297 ms 50424 KB Output is correct
14 Correct 233 ms 52604 KB Output is correct
15 Correct 219 ms 40184 KB Output is correct
16 Correct 354 ms 50696 KB Output is correct
17 Correct 341 ms 47656 KB Output is correct
18 Correct 368 ms 54496 KB Output is correct
19 Correct 340 ms 52320 KB Output is correct
20 Correct 245 ms 38860 KB Output is correct
21 Correct 241 ms 39880 KB Output is correct
22 Correct 248 ms 39544 KB Output is correct
23 Correct 250 ms 39756 KB Output is correct
24 Correct 260 ms 39652 KB Output is correct
25 Correct 239 ms 38788 KB Output is correct
26 Correct 243 ms 39516 KB Output is correct
27 Correct 239 ms 38556 KB Output is correct
28 Incorrect 10 ms 12928 KB Output isn't correct
29 Halted 0 ms 0 KB -