oj.uz

Submission #1070673

# Submission time Handle Problem Language Result Execution time Memory
1070673 2024-08-22T16:44:46 Z TVSown Swapping Cities (APIO20_swap) C++17
6 / 100
 465 ms 84152 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 7 ms 57948 KB Output is correct
2 Correct 9 ms 55900 KB Output is correct
3 Correct 11 ms 55900 KB Output is correct
4 Correct 7 ms 55896 KB Output is correct
5 Correct 7 ms 55900 KB Output is correct
6 Correct 11 ms 57948 KB Output is correct
7 Correct 7 ms 55900 KB Output is correct
8 Correct 9 ms 57948 KB Output is correct
9 Correct 83 ms 71764 KB Output is correct
10 Correct 72 ms 75864 KB Output is correct
11 Correct 72 ms 76900 KB Output is correct
12 Correct 72 ms 79256 KB Output is correct
13 Correct 66 ms 80980 KB Output is correct
14 Correct 69 ms 73136 KB Output is correct
15 Correct 200 ms 79064 KB Output is correct
16 Correct 203 ms 78596 KB Output is correct
17 Correct 207 ms 80828 KB Output is correct
18 Correct 368 ms 84152 KB Output is correct
19 Correct 100 ms 68176 KB Output is correct
20 Correct 185 ms 78756 KB Output is correct
21 Correct 224 ms 78124 KB Output is correct
22 Correct 169 ms 81080 KB Output is correct
23 Correct 445 ms 82868 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 57948 KB Output is correct
2 Correct 9 ms 55900 KB Output is correct
3 Incorrect 465 ms 83952 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 57948 KB Output is correct
2 Correct 9 ms 55900 KB Output is correct
3 Correct 11 ms 55900 KB Output is correct
4 Correct 7 ms 55896 KB Output is correct
5 Correct 7 ms 55900 KB Output is correct
6 Correct 11 ms 57948 KB Output is correct
7 Correct 7 ms 55900 KB Output is correct
8 Correct 9 ms 57948 KB Output is correct
9 Correct 9 ms 51800 KB Output is correct
10 Incorrect 8 ms 51800 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 51800 KB Output is correct
2 Correct 7 ms 57948 KB Output is correct
3 Correct 9 ms 55900 KB Output is correct
4 Correct 11 ms 55900 KB Output is correct
5 Correct 7 ms 55896 KB Output is correct
6 Correct 7 ms 55900 KB Output is correct
7 Correct 11 ms 57948 KB Output is correct
8 Correct 7 ms 55900 KB Output is correct
9 Correct 9 ms 57948 KB Output is correct
10 Correct 83 ms 71764 KB Output is correct
11 Correct 72 ms 75864 KB Output is correct
12 Correct 72 ms 76900 KB Output is correct
13 Correct 72 ms 79256 KB Output is correct
14 Correct 66 ms 80980 KB Output is correct
15 Incorrect 8 ms 51800 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 57948 KB Output is correct
2 Correct 9 ms 55900 KB Output is correct
3 Correct 11 ms 55900 KB Output is correct
4 Correct 7 ms 55896 KB Output is correct
5 Correct 7 ms 55900 KB Output is correct
6 Correct 11 ms 57948 KB Output is correct
7 Correct 7 ms 55900 KB Output is correct
8 Correct 9 ms 57948 KB Output is correct
9 Correct 83 ms 71764 KB Output is correct
10 Correct 72 ms 75864 KB Output is correct
11 Correct 72 ms 76900 KB Output is correct
12 Correct 72 ms 79256 KB Output is correct
13 Correct 66 ms 80980 KB Output is correct
14 Correct 69 ms 73136 KB Output is correct
15 Correct 200 ms 79064 KB Output is correct
16 Correct 203 ms 78596 KB Output is correct
17 Correct 207 ms 80828 KB Output is correct
18 Correct 368 ms 84152 KB Output is correct
19 Incorrect 465 ms 83952 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 51800 KB Output is correct
2 Correct 7 ms 57948 KB Output is correct
3 Correct 9 ms 55900 KB Output is correct
4 Correct 11 ms 55900 KB Output is correct
5 Correct 7 ms 55896 KB Output is correct
6 Correct 7 ms 55900 KB Output is correct
7 Correct 11 ms 57948 KB Output is correct
8 Correct 7 ms 55900 KB Output is correct
9 Correct 9 ms 57948 KB Output is correct
10 Correct 83 ms 71764 KB Output is correct
11 Correct 72 ms 75864 KB Output is correct
12 Correct 72 ms 76900 KB Output is correct
13 Correct 72 ms 79256 KB Output is correct
14 Correct 66 ms 80980 KB Output is correct
15 Correct 69 ms 73136 KB Output is correct
16 Correct 200 ms 79064 KB Output is correct
17 Correct 203 ms 78596 KB Output is correct
18 Correct 207 ms 80828 KB Output is correct
19 Correct 368 ms 84152 KB Output is correct
20 Incorrect 465 ms 83952 KB Output isn't correct
21 Halted 0 ms 0 KB -