oj.uz

Submission #1069229

# Submission time Handle Problem Language Result Execution time Memory
1069229 2024-08-21T17:47:41 Z TVSown Swapping Cities (APIO20_swap) C++17
6 / 100
 478 ms 64516 KB 
///*** Sown_Vipro ***///
/// ->TUYEN QUOC GIA<- ///

#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("popcnt")
#define F first
#define S second
#define pb push_back
#define pi pair<int, int>
#define pii pair<int, pair<int, int> >
#define all(a) a.begin(), a.end()
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = a; i >= b; --i)
#define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin);
#define out(name) if(fopen(name, "w")) freopen(name, "w", stdout);
#define szz(s) int(s.size())
const int N = 1e6 + 5, MAX = 1e6, oo = 1e9 + 5, MOD = 1e9 + 7;
int n, nn, m;
int p[N], b[N], check[N], nxt[25][N], h[N];
vector<int> adj[N];

struct edge{
    int u, v, w;
} e[N];

bool cmp(edge a, edge b){
    return a.w < b.w;
}

int Find(int u){
    if(u == p[u]) return u;
    return p[u] = Find(p[u]);
}

void Union(int u, int v){
    ++b[u]; ++b[v];
    int uu = u, vv = v;
    ++n;
    p[n] = n;
    u = Find(u); v = Find(v);
    if(u == v){
        p[u] = n;
        adj[u].pb(n);
        adj[n].pb(u);
        check[n] = 1;
    }else{
        p[u] = n; p[v] = n;
        check[n] = (check[u] || check[v] || b[uu] > 2 || b[vv] > 2);
        adj[u].pb(n);
        adj[n].pb(u);
        adj[v].pb(n);
        adj[n].pb(v);
    }
}

void dfs(int u){
    for(int v : adj[u]){
        if(v == nxt[0][u]) continue;
        h[v] = h[u] + 1;
        nxt[0][v] = u;
        dfs(v);
    }
}

int lca(int u, int v){
    if(h[u] < h[v]) swap(u, v);
    REP(k, 20, 0){
        int pu = nxt[k][u];
        if(h[pu] >= h[v]){
            u = pu;
        }
    }
    if(u == v) return u;

    REP(k, 20, 0){
        int pu = nxt[k][u], pv = nxt[k][v];
        if(pu != pv){
            u = pu; v = pv;
        }
    }
    return nxt[0][u];
}

int lift(int u, int mid){
    REP(k, 20, 0){
        if((1 << k) <= mid){
            u = nxt[k][u];
            mid -= (1 << k);
        }
    }
    return u;
}

int getMinimumFuelCapacity(int u, int v){
    int p = lca(u, v);
    int l = 0, r = h[p];

    while(l <= r){
        int mid = (l + r) / 2;
        if(check[lift(p, mid)]) r = mid - 1;
        else l = mid + 1;
    }

    if(l > h[p]) return -1;
    return e[lift(p, l) - nn].w;
}

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W){
    n = N; m = M;
    nn = N;
    FOR(i, 1, m){
        e[i] = {U[i - 1], V[i - 1], W[i - 1]};
    }
    sort(e + 1, e + 1 + m, cmp);
    FOR(u, 0, n) p[u] = u;
    FOR(i, 1, m){
        int u = e[i].u, v = e[i].v;

        Union(u, v);
    }
    h[n] = 1;
    dfs(n);

    FOR(k, 1, 20){
        FOR(u, 0, n){
            nxt[k][u] = nxt[k - 1][nxt[k - 1][u]];
        }
    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25688 KB Output is correct
2 Correct 10 ms 25180 KB Output is correct
3 Correct 9 ms 25432 KB Output is correct
4 Correct 10 ms 25532 KB Output is correct
5 Correct 9 ms 25536 KB Output is correct
6 Correct 10 ms 25628 KB Output is correct
7 Correct 11 ms 25692 KB Output is correct
8 Correct 11 ms 25696 KB Output is correct
9 Correct 68 ms 47824 KB Output is correct
10 Correct 77 ms 52820 KB Output is correct
11 Correct 73 ms 52304 KB Output is correct
12 Correct 74 ms 53840 KB Output is correct
13 Correct 70 ms 57052 KB Output is correct
14 Correct 80 ms 47700 KB Output is correct
15 Correct 185 ms 54708 KB Output is correct
16 Correct 176 ms 53932 KB Output is correct
17 Correct 222 ms 55548 KB Output is correct
18 Correct 422 ms 58800 KB Output is correct
19 Correct 101 ms 33360 KB Output is correct
20 Correct 186 ms 60116 KB Output is correct
21 Correct 193 ms 59404 KB Output is correct
22 Correct 183 ms 61624 KB Output is correct
23 Correct 432 ms 64516 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25688 KB Output is correct
2 Correct 10 ms 25180 KB Output is correct
3 Incorrect 478 ms 61168 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25688 KB Output is correct
2 Correct 10 ms 25180 KB Output is correct
3 Correct 9 ms 25432 KB Output is correct
4 Correct 10 ms 25532 KB Output is correct
5 Correct 9 ms 25536 KB Output is correct
6 Correct 10 ms 25628 KB Output is correct
7 Correct 11 ms 25692 KB Output is correct
8 Correct 11 ms 25696 KB Output is correct
9 Correct 10 ms 25436 KB Output is correct
10 Incorrect 10 ms 25528 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 25436 KB Output is correct
2 Correct 13 ms 25688 KB Output is correct
3 Correct 10 ms 25180 KB Output is correct
4 Correct 9 ms 25432 KB Output is correct
5 Correct 10 ms 25532 KB Output is correct
6 Correct 9 ms 25536 KB Output is correct
7 Correct 10 ms 25628 KB Output is correct
8 Correct 11 ms 25692 KB Output is correct
9 Correct 11 ms 25696 KB Output is correct
10 Correct 68 ms 47824 KB Output is correct
11 Correct 77 ms 52820 KB Output is correct
12 Correct 73 ms 52304 KB Output is correct
13 Correct 74 ms 53840 KB Output is correct
14 Correct 70 ms 57052 KB Output is correct
15 Incorrect 10 ms 25528 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25688 KB Output is correct
2 Correct 10 ms 25180 KB Output is correct
3 Correct 9 ms 25432 KB Output is correct
4 Correct 10 ms 25532 KB Output is correct
5 Correct 9 ms 25536 KB Output is correct
6 Correct 10 ms 25628 KB Output is correct
7 Correct 11 ms 25692 KB Output is correct
8 Correct 11 ms 25696 KB Output is correct
9 Correct 68 ms 47824 KB Output is correct
10 Correct 77 ms 52820 KB Output is correct
11 Correct 73 ms 52304 KB Output is correct
12 Correct 74 ms 53840 KB Output is correct
13 Correct 70 ms 57052 KB Output is correct
14 Correct 80 ms 47700 KB Output is correct
15 Correct 185 ms 54708 KB Output is correct
16 Correct 176 ms 53932 KB Output is correct
17 Correct 222 ms 55548 KB Output is correct
18 Correct 422 ms 58800 KB Output is correct
19 Incorrect 478 ms 61168 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 25436 KB Output is correct
2 Correct 13 ms 25688 KB Output is correct
3 Correct 10 ms 25180 KB Output is correct
4 Correct 9 ms 25432 KB Output is correct
5 Correct 10 ms 25532 KB Output is correct
6 Correct 9 ms 25536 KB Output is correct
7 Correct 10 ms 25628 KB Output is correct
8 Correct 11 ms 25692 KB Output is correct
9 Correct 11 ms 25696 KB Output is correct
10 Correct 68 ms 47824 KB Output is correct
11 Correct 77 ms 52820 KB Output is correct
12 Correct 73 ms 52304 KB Output is correct
13 Correct 74 ms 53840 KB Output is correct
14 Correct 70 ms 57052 KB Output is correct
15 Correct 80 ms 47700 KB Output is correct
16 Correct 185 ms 54708 KB Output is correct
17 Correct 176 ms 53932 KB Output is correct
18 Correct 222 ms 55548 KB Output is correct
19 Correct 422 ms 58800 KB Output is correct
20 Incorrect 478 ms 61168 KB Output isn't correct
21 Halted 0 ms 0 KB -