oj.uz

Submission #1069851

# Submission time Handle Problem Language Result Execution time Memory
1069851 2024-08-22T09:23:49 Z TVSown Swapping Cities (APIO20_swap) C++17
6 / 100
 648 ms 136380 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<long long, 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;
long long p[N], b[N], check[N], nxt[25][N], h[N];
vector<long long> adj[N];

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

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

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

void Union(long long u, long long v){
    ++b[u]; ++b[v];
    long long 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(long long u){
    for(long long v : adj[u]){
        if(v == nxt[0][u]) continue;
        h[v] = h[u] + 1;
        nxt[0][v] = u;
        dfs(v);
    }
}

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

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

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

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

    while(l <= r){
        long long 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){
        long long u = e[i].u, v = e[i].v;

        Union(u, v);
    }

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

    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 10 ms 72148 KB Output is correct
2 Correct 10 ms 72140 KB Output is correct
3 Correct 11 ms 72204 KB Output is correct
4 Correct 11 ms 72280 KB Output is correct
5 Correct 9 ms 72388 KB Output is correct
6 Correct 8 ms 72284 KB Output is correct
7 Correct 10 ms 72284 KB Output is correct
8 Correct 11 ms 72284 KB Output is correct
9 Correct 86 ms 115796 KB Output is correct
10 Correct 100 ms 126288 KB Output is correct
11 Correct 122 ms 123980 KB Output is correct
12 Correct 94 ms 128848 KB Output is correct
13 Correct 71 ms 130896 KB Output is correct
14 Correct 116 ms 115948 KB Output is correct
15 Correct 209 ms 130376 KB Output is correct
16 Correct 207 ms 128112 KB Output is correct
17 Correct 286 ms 132948 KB Output is correct
18 Correct 520 ms 134944 KB Output is correct
19 Correct 109 ms 87632 KB Output is correct
20 Correct 240 ms 131536 KB Output is correct
21 Correct 261 ms 127240 KB Output is correct
22 Correct 194 ms 134328 KB Output is correct
23 Correct 586 ms 136380 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 72148 KB Output is correct
2 Correct 10 ms 72140 KB Output is correct
3 Incorrect 648 ms 132976 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 72148 KB Output is correct
2 Correct 10 ms 72140 KB Output is correct
3 Correct 11 ms 72204 KB Output is correct
4 Correct 11 ms 72280 KB Output is correct
5 Correct 9 ms 72388 KB Output is correct
6 Correct 8 ms 72284 KB Output is correct
7 Correct 10 ms 72284 KB Output is correct
8 Correct 11 ms 72284 KB Output is correct
9 Correct 8 ms 72028 KB Output is correct
10 Incorrect 9 ms 72284 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 72028 KB Output is correct
2 Correct 10 ms 72148 KB Output is correct
3 Correct 10 ms 72140 KB Output is correct
4 Correct 11 ms 72204 KB Output is correct
5 Correct 11 ms 72280 KB Output is correct
6 Correct 9 ms 72388 KB Output is correct
7 Correct 8 ms 72284 KB Output is correct
8 Correct 10 ms 72284 KB Output is correct
9 Correct 11 ms 72284 KB Output is correct
10 Correct 86 ms 115796 KB Output is correct
11 Correct 100 ms 126288 KB Output is correct
12 Correct 122 ms 123980 KB Output is correct
13 Correct 94 ms 128848 KB Output is correct
14 Correct 71 ms 130896 KB Output is correct
15 Incorrect 9 ms 72284 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 72148 KB Output is correct
2 Correct 10 ms 72140 KB Output is correct
3 Correct 11 ms 72204 KB Output is correct
4 Correct 11 ms 72280 KB Output is correct
5 Correct 9 ms 72388 KB Output is correct
6 Correct 8 ms 72284 KB Output is correct
7 Correct 10 ms 72284 KB Output is correct
8 Correct 11 ms 72284 KB Output is correct
9 Correct 86 ms 115796 KB Output is correct
10 Correct 100 ms 126288 KB Output is correct
11 Correct 122 ms 123980 KB Output is correct
12 Correct 94 ms 128848 KB Output is correct
13 Correct 71 ms 130896 KB Output is correct
14 Correct 116 ms 115948 KB Output is correct
15 Correct 209 ms 130376 KB Output is correct
16 Correct 207 ms 128112 KB Output is correct
17 Correct 286 ms 132948 KB Output is correct
18 Correct 520 ms 134944 KB Output is correct
19 Incorrect 648 ms 132976 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 72028 KB Output is correct
2 Correct 10 ms 72148 KB Output is correct
3 Correct 10 ms 72140 KB Output is correct
4 Correct 11 ms 72204 KB Output is correct
5 Correct 11 ms 72280 KB Output is correct
6 Correct 9 ms 72388 KB Output is correct
7 Correct 8 ms 72284 KB Output is correct
8 Correct 10 ms 72284 KB Output is correct
9 Correct 11 ms 72284 KB Output is correct
10 Correct 86 ms 115796 KB Output is correct
11 Correct 100 ms 126288 KB Output is correct
12 Correct 122 ms 123980 KB Output is correct
13 Correct 94 ms 128848 KB Output is correct
14 Correct 71 ms 130896 KB Output is correct
15 Correct 116 ms 115948 KB Output is correct
16 Correct 209 ms 130376 KB Output is correct
17 Correct 207 ms 128112 KB Output is correct
18 Correct 286 ms 132948 KB Output is correct
19 Correct 520 ms 134944 KB Output is correct
20 Incorrect 648 ms 132976 KB Output isn't correct
21 Halted 0 ms 0 KB -