oj.uz

Submission #1069226

# Submission time Handle Problem Language Result Execution time Memory
1069226 2024-08-21T17:47:16 Z TVSown Swapping Cities (APIO20_swap) C++17
0 / 100
 583 ms 60024 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;
    if(lift(p, l) >= nn) 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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 25176 KB Output is correct
2 Correct 10 ms 25180 KB Output is correct
3 Correct 9 ms 25316 KB Output is correct
4 Correct 10 ms 25436 KB Output is correct
5 Correct 11 ms 25452 KB Output is correct
6 Correct 10 ms 25432 KB Output is correct
7 Correct 10 ms 25692 KB Output is correct
8 Correct 10 ms 25700 KB Output is correct
9 Correct 66 ms 47828 KB Output is correct
10 Correct 75 ms 52816 KB Output is correct
11 Correct 88 ms 52392 KB Output is correct
12 Correct 101 ms 53840 KB Output is correct
13 Correct 91 ms 56916 KB Output is correct
14 Correct 74 ms 47696 KB Output is correct
15 Correct 186 ms 54748 KB Output is correct
16 Correct 191 ms 54020 KB Output is correct
17 Correct 211 ms 55732 KB Output is correct
18 Correct 426 ms 58808 KB Output is correct
19 Incorrect 113 ms 32084 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 25176 KB Output is correct
2 Correct 10 ms 25180 KB Output is correct
3 Incorrect 583 ms 60024 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 25176 KB Output is correct
2 Correct 10 ms 25180 KB Output is correct
3 Correct 9 ms 25316 KB Output is correct
4 Correct 10 ms 25436 KB Output is correct
5 Correct 11 ms 25452 KB Output is correct
6 Correct 10 ms 25432 KB Output is correct
7 Correct 10 ms 25692 KB Output is correct
8 Correct 10 ms 25700 KB Output is correct
9 Incorrect 10 ms 25228 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 25228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 25176 KB Output is correct
2 Correct 10 ms 25180 KB Output is correct
3 Correct 9 ms 25316 KB Output is correct
4 Correct 10 ms 25436 KB Output is correct
5 Correct 11 ms 25452 KB Output is correct
6 Correct 10 ms 25432 KB Output is correct
7 Correct 10 ms 25692 KB Output is correct
8 Correct 10 ms 25700 KB Output is correct
9 Correct 66 ms 47828 KB Output is correct
10 Correct 75 ms 52816 KB Output is correct
11 Correct 88 ms 52392 KB Output is correct
12 Correct 101 ms 53840 KB Output is correct
13 Correct 91 ms 56916 KB Output is correct
14 Correct 74 ms 47696 KB Output is correct
15 Correct 186 ms 54748 KB Output is correct
16 Correct 191 ms 54020 KB Output is correct
17 Correct 211 ms 55732 KB Output is correct
18 Correct 426 ms 58808 KB Output is correct
19 Incorrect 583 ms 60024 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 25228 KB Output isn't correct
2 Halted 0 ms 0 KB -