oj.uz

Submission #1070678

# Submission time Handle Problem Language Result Execution time Memory
1070678 2024-08-22T16:45:39 Z TVSown Swapping Cities (APIO20_swap) C++17
6 / 100
 382 ms 88516 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 + 1){
            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 53848 KB Output is correct
2 Correct 6 ms 51804 KB Output is correct
3 Correct 9 ms 51804 KB Output is correct
4 Correct 6 ms 51804 KB Output is correct
5 Correct 9 ms 51916 KB Output is correct
6 Correct 7 ms 51800 KB Output is correct
7 Correct 7 ms 53852 KB Output is correct
8 Correct 8 ms 58200 KB Output is correct
9 Correct 57 ms 71572 KB Output is correct
10 Correct 98 ms 73300 KB Output is correct
11 Correct 67 ms 72900 KB Output is correct
12 Correct 74 ms 75348 KB Output is correct
13 Correct 62 ms 79840 KB Output is correct
14 Correct 67 ms 70228 KB Output is correct
15 Correct 166 ms 76536 KB Output is correct
16 Correct 159 ms 77308 KB Output is correct
17 Correct 206 ms 83380 KB Output is correct
18 Correct 382 ms 85432 KB Output is correct
19 Correct 93 ms 68180 KB Output is correct
20 Correct 195 ms 81620 KB Output is correct
21 Correct 187 ms 81164 KB Output is correct
22 Correct 164 ms 82356 KB Output is correct
23 Correct 379 ms 85364 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 53848 KB Output is correct
2 Correct 6 ms 51804 KB Output is correct
3 Incorrect 377 ms 88516 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 53848 KB Output is correct
2 Correct 6 ms 51804 KB Output is correct
3 Correct 9 ms 51804 KB Output is correct
4 Correct 6 ms 51804 KB Output is correct
5 Correct 9 ms 51916 KB Output is correct
6 Correct 7 ms 51800 KB Output is correct
7 Correct 7 ms 53852 KB Output is correct
8 Correct 8 ms 58200 KB Output is correct
9 Correct 7 ms 59996 KB Output is correct
10 Incorrect 8 ms 61968 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 59996 KB Output is correct
2 Correct 7 ms 53848 KB Output is correct
3 Correct 6 ms 51804 KB Output is correct
4 Correct 9 ms 51804 KB Output is correct
5 Correct 6 ms 51804 KB Output is correct
6 Correct 9 ms 51916 KB Output is correct
7 Correct 7 ms 51800 KB Output is correct
8 Correct 7 ms 53852 KB Output is correct
9 Correct 8 ms 58200 KB Output is correct
10 Correct 57 ms 71572 KB Output is correct
11 Correct 98 ms 73300 KB Output is correct
12 Correct 67 ms 72900 KB Output is correct
13 Correct 74 ms 75348 KB Output is correct
14 Correct 62 ms 79840 KB Output is correct
15 Incorrect 8 ms 61968 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 53848 KB Output is correct
2 Correct 6 ms 51804 KB Output is correct
3 Correct 9 ms 51804 KB Output is correct
4 Correct 6 ms 51804 KB Output is correct
5 Correct 9 ms 51916 KB Output is correct
6 Correct 7 ms 51800 KB Output is correct
7 Correct 7 ms 53852 KB Output is correct
8 Correct 8 ms 58200 KB Output is correct
9 Correct 57 ms 71572 KB Output is correct
10 Correct 98 ms 73300 KB Output is correct
11 Correct 67 ms 72900 KB Output is correct
12 Correct 74 ms 75348 KB Output is correct
13 Correct 62 ms 79840 KB Output is correct
14 Correct 67 ms 70228 KB Output is correct
15 Correct 166 ms 76536 KB Output is correct
16 Correct 159 ms 77308 KB Output is correct
17 Correct 206 ms 83380 KB Output is correct
18 Correct 382 ms 85432 KB Output is correct
19 Incorrect 377 ms 88516 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 59996 KB Output is correct
2 Correct 7 ms 53848 KB Output is correct
3 Correct 6 ms 51804 KB Output is correct
4 Correct 9 ms 51804 KB Output is correct
5 Correct 6 ms 51804 KB Output is correct
6 Correct 9 ms 51916 KB Output is correct
7 Correct 7 ms 51800 KB Output is correct
8 Correct 7 ms 53852 KB Output is correct
9 Correct 8 ms 58200 KB Output is correct
10 Correct 57 ms 71572 KB Output is correct
11 Correct 98 ms 73300 KB Output is correct
12 Correct 67 ms 72900 KB Output is correct
13 Correct 74 ms 75348 KB Output is correct
14 Correct 62 ms 79840 KB Output is correct
15 Correct 67 ms 70228 KB Output is correct
16 Correct 166 ms 76536 KB Output is correct
17 Correct 159 ms 77308 KB Output is correct
18 Correct 206 ms 83380 KB Output is correct
19 Correct 382 ms 85432 KB Output is correct
20 Incorrect 377 ms 88516 KB Output isn't correct
21 Halted 0 ms 0 KB -