oj.uz

답안 #1070679

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1070679 2024-08-22T16:45:52 Z vjudge1 자매 도시 (APIO20_swap) C++17
6 / 100
 461 ms 88356 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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 31320 KB Output is correct
2 Correct 6 ms 33372 KB Output is correct
3 Correct 4 ms 33372 KB Output is correct
4 Correct 5 ms 33372 KB Output is correct
5 Correct 5 ms 33480 KB Output is correct
6 Correct 9 ms 41820 KB Output is correct
7 Correct 7 ms 39644 KB Output is correct
8 Correct 8 ms 31580 KB Output is correct
9 Correct 62 ms 53332 KB Output is correct
10 Correct 70 ms 57936 KB Output is correct
11 Correct 106 ms 57424 KB Output is correct
12 Correct 98 ms 60756 KB Output is correct
13 Correct 93 ms 78420 KB Output is correct
14 Correct 70 ms 70292 KB Output is correct
15 Correct 200 ms 76520 KB Output is correct
16 Correct 188 ms 78584 KB Output is correct
17 Correct 245 ms 78432 KB Output is correct
18 Correct 392 ms 81568 KB Output is correct
19 Correct 98 ms 62352 KB Output is correct
20 Correct 175 ms 80340 KB Output is correct
21 Correct 185 ms 81144 KB Output is correct
22 Correct 173 ms 84916 KB Output is correct
23 Correct 461 ms 86708 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 31320 KB Output is correct
2 Correct 6 ms 33372 KB Output is correct
3 Incorrect 401 ms 88356 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 31320 KB Output is correct
2 Correct 6 ms 33372 KB Output is correct
3 Correct 4 ms 33372 KB Output is correct
4 Correct 5 ms 33372 KB Output is correct
5 Correct 5 ms 33480 KB Output is correct
6 Correct 9 ms 41820 KB Output is correct
7 Correct 7 ms 39644 KB Output is correct
8 Correct 8 ms 31580 KB Output is correct
9 Correct 7 ms 62040 KB Output is correct
10 Incorrect 9 ms 59996 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 62040 KB Output is correct
2 Correct 4 ms 31320 KB Output is correct
3 Correct 6 ms 33372 KB Output is correct
4 Correct 4 ms 33372 KB Output is correct
5 Correct 5 ms 33372 KB Output is correct
6 Correct 5 ms 33480 KB Output is correct
7 Correct 9 ms 41820 KB Output is correct
8 Correct 7 ms 39644 KB Output is correct
9 Correct 8 ms 31580 KB Output is correct
10 Correct 62 ms 53332 KB Output is correct
11 Correct 70 ms 57936 KB Output is correct
12 Correct 106 ms 57424 KB Output is correct
13 Correct 98 ms 60756 KB Output is correct
14 Correct 93 ms 78420 KB Output is correct
15 Incorrect 9 ms 59996 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 31320 KB Output is correct
2 Correct 6 ms 33372 KB Output is correct
3 Correct 4 ms 33372 KB Output is correct
4 Correct 5 ms 33372 KB Output is correct
5 Correct 5 ms 33480 KB Output is correct
6 Correct 9 ms 41820 KB Output is correct
7 Correct 7 ms 39644 KB Output is correct
8 Correct 8 ms 31580 KB Output is correct
9 Correct 62 ms 53332 KB Output is correct
10 Correct 70 ms 57936 KB Output is correct
11 Correct 106 ms 57424 KB Output is correct
12 Correct 98 ms 60756 KB Output is correct
13 Correct 93 ms 78420 KB Output is correct
14 Correct 70 ms 70292 KB Output is correct
15 Correct 200 ms 76520 KB Output is correct
16 Correct 188 ms 78584 KB Output is correct
17 Correct 245 ms 78432 KB Output is correct
18 Correct 392 ms 81568 KB Output is correct
19 Incorrect 401 ms 88356 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 62040 KB Output is correct
2 Correct 4 ms 31320 KB Output is correct
3 Correct 6 ms 33372 KB Output is correct
4 Correct 4 ms 33372 KB Output is correct
5 Correct 5 ms 33372 KB Output is correct
6 Correct 5 ms 33480 KB Output is correct
7 Correct 9 ms 41820 KB Output is correct
8 Correct 7 ms 39644 KB Output is correct
9 Correct 8 ms 31580 KB Output is correct
10 Correct 62 ms 53332 KB Output is correct
11 Correct 70 ms 57936 KB Output is correct
12 Correct 106 ms 57424 KB Output is correct
13 Correct 98 ms 60756 KB Output is correct
14 Correct 93 ms 78420 KB Output is correct
15 Correct 70 ms 70292 KB Output is correct
16 Correct 200 ms 76520 KB Output is correct
17 Correct 188 ms 78584 KB Output is correct
18 Correct 245 ms 78432 KB Output is correct
19 Correct 392 ms 81568 KB Output is correct
20 Incorrect 401 ms 88356 KB Output isn't correct
21 Halted 0 ms 0 KB -