oj.uz

Submission #1069233

# Submission time Handle Problem Language Result Execution time Memory
1069233 2024-08-21T17:51:31 Z TVSown Swapping Cities (APIO20_swap) C++17
6 / 100
 643 ms 82908 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);
    }
    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 11 ms 24668 KB Output is correct
2 Correct 11 ms 24848 KB Output is correct
3 Correct 9 ms 24668 KB Output is correct
4 Correct 10 ms 24920 KB Output is correct
5 Correct 10 ms 25180 KB Output is correct
6 Correct 10 ms 25180 KB Output is correct
7 Correct 10 ms 25180 KB Output is correct
8 Correct 9 ms 25320 KB Output is correct
9 Correct 80 ms 65288 KB Output is correct
10 Correct 95 ms 74620 KB Output is correct
11 Correct 100 ms 73556 KB Output is correct
12 Correct 112 ms 76552 KB Output is correct
13 Correct 81 ms 78420 KB Output is correct
14 Correct 97 ms 65624 KB Output is correct
15 Correct 247 ms 77788 KB Output is correct
16 Correct 258 ms 76544 KB Output is correct
17 Correct 341 ms 79540 KB Output is correct
18 Correct 607 ms 81592 KB Output is correct
19 Correct 120 ms 37512 KB Output is correct
20 Correct 282 ms 79144 KB Output is correct
21 Correct 269 ms 77420 KB Output is correct
22 Correct 245 ms 80868 KB Output is correct
23 Correct 581 ms 82908 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24668 KB Output is correct
2 Correct 11 ms 24848 KB Output is correct
3 Incorrect 643 ms 81672 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24668 KB Output is correct
2 Correct 11 ms 24848 KB Output is correct
3 Correct 9 ms 24668 KB Output is correct
4 Correct 10 ms 24920 KB Output is correct
5 Correct 10 ms 25180 KB Output is correct
6 Correct 10 ms 25180 KB Output is correct
7 Correct 10 ms 25180 KB Output is correct
8 Correct 9 ms 25320 KB Output is correct
9 Correct 10 ms 24668 KB Output is correct
10 Incorrect 10 ms 25180 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 24668 KB Output is correct
2 Correct 11 ms 24668 KB Output is correct
3 Correct 11 ms 24848 KB Output is correct
4 Correct 9 ms 24668 KB Output is correct
5 Correct 10 ms 24920 KB Output is correct
6 Correct 10 ms 25180 KB Output is correct
7 Correct 10 ms 25180 KB Output is correct
8 Correct 10 ms 25180 KB Output is correct
9 Correct 9 ms 25320 KB Output is correct
10 Correct 80 ms 65288 KB Output is correct
11 Correct 95 ms 74620 KB Output is correct
12 Correct 100 ms 73556 KB Output is correct
13 Correct 112 ms 76552 KB Output is correct
14 Correct 81 ms 78420 KB Output is correct
15 Incorrect 10 ms 25180 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24668 KB Output is correct
2 Correct 11 ms 24848 KB Output is correct
3 Correct 9 ms 24668 KB Output is correct
4 Correct 10 ms 24920 KB Output is correct
5 Correct 10 ms 25180 KB Output is correct
6 Correct 10 ms 25180 KB Output is correct
7 Correct 10 ms 25180 KB Output is correct
8 Correct 9 ms 25320 KB Output is correct
9 Correct 80 ms 65288 KB Output is correct
10 Correct 95 ms 74620 KB Output is correct
11 Correct 100 ms 73556 KB Output is correct
12 Correct 112 ms 76552 KB Output is correct
13 Correct 81 ms 78420 KB Output is correct
14 Correct 97 ms 65624 KB Output is correct
15 Correct 247 ms 77788 KB Output is correct
16 Correct 258 ms 76544 KB Output is correct
17 Correct 341 ms 79540 KB Output is correct
18 Correct 607 ms 81592 KB Output is correct
19 Incorrect 643 ms 81672 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 24668 KB Output is correct
2 Correct 11 ms 24668 KB Output is correct
3 Correct 11 ms 24848 KB Output is correct
4 Correct 9 ms 24668 KB Output is correct
5 Correct 10 ms 24920 KB Output is correct
6 Correct 10 ms 25180 KB Output is correct
7 Correct 10 ms 25180 KB Output is correct
8 Correct 10 ms 25180 KB Output is correct
9 Correct 9 ms 25320 KB Output is correct
10 Correct 80 ms 65288 KB Output is correct
11 Correct 95 ms 74620 KB Output is correct
12 Correct 100 ms 73556 KB Output is correct
13 Correct 112 ms 76552 KB Output is correct
14 Correct 81 ms 78420 KB Output is correct
15 Correct 97 ms 65624 KB Output is correct
16 Correct 247 ms 77788 KB Output is correct
17 Correct 258 ms 76544 KB Output is correct
18 Correct 341 ms 79540 KB Output is correct
19 Correct 607 ms 81592 KB Output is correct
20 Incorrect 643 ms 81672 KB Output isn't correct
21 Halted 0 ms 0 KB -