oj.uz

답안 #1070674

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

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 49692 KB Output is correct
2 Correct 10 ms 51800 KB Output is correct
3 Correct 8 ms 47708 KB Output is correct
4 Correct 6 ms 35420 KB Output is correct
5 Correct 10 ms 43868 KB Output is correct
6 Correct 9 ms 49752 KB Output is correct
7 Correct 10 ms 45916 KB Output is correct
8 Correct 10 ms 49932 KB Output is correct
9 Correct 92 ms 69840 KB Output is correct
10 Correct 85 ms 73320 KB Output is correct
11 Correct 79 ms 75596 KB Output is correct
12 Correct 85 ms 69232 KB Output is correct
13 Correct 76 ms 81116 KB Output is correct
14 Correct 69 ms 71672 KB Output is correct
15 Correct 188 ms 81372 KB Output is correct
16 Correct 185 ms 80920 KB Output is correct
17 Correct 219 ms 82156 KB Output is correct
18 Correct 471 ms 87956 KB Output is correct
19 Correct 101 ms 53784 KB Output is correct
20 Correct 228 ms 80340 KB Output is correct
21 Correct 182 ms 81136 KB Output is correct
22 Correct 188 ms 81136 KB Output is correct
23 Correct 423 ms 74080 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 49692 KB Output is correct
2 Correct 10 ms 51800 KB Output is correct
3 Incorrect 474 ms 85748 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 49692 KB Output is correct
2 Correct 10 ms 51800 KB Output is correct
3 Correct 8 ms 47708 KB Output is correct
4 Correct 6 ms 35420 KB Output is correct
5 Correct 10 ms 43868 KB Output is correct
6 Correct 9 ms 49752 KB Output is correct
7 Correct 10 ms 45916 KB Output is correct
8 Correct 10 ms 49932 KB Output is correct
9 Correct 8 ms 57944 KB Output is correct
10 Incorrect 7 ms 51804 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 57944 KB Output is correct
2 Correct 10 ms 49692 KB Output is correct
3 Correct 10 ms 51800 KB Output is correct
4 Correct 8 ms 47708 KB Output is correct
5 Correct 6 ms 35420 KB Output is correct
6 Correct 10 ms 43868 KB Output is correct
7 Correct 9 ms 49752 KB Output is correct
8 Correct 10 ms 45916 KB Output is correct
9 Correct 10 ms 49932 KB Output is correct
10 Correct 92 ms 69840 KB Output is correct
11 Correct 85 ms 73320 KB Output is correct
12 Correct 79 ms 75596 KB Output is correct
13 Correct 85 ms 69232 KB Output is correct
14 Correct 76 ms 81116 KB Output is correct
15 Incorrect 7 ms 51804 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 49692 KB Output is correct
2 Correct 10 ms 51800 KB Output is correct
3 Correct 8 ms 47708 KB Output is correct
4 Correct 6 ms 35420 KB Output is correct
5 Correct 10 ms 43868 KB Output is correct
6 Correct 9 ms 49752 KB Output is correct
7 Correct 10 ms 45916 KB Output is correct
8 Correct 10 ms 49932 KB Output is correct
9 Correct 92 ms 69840 KB Output is correct
10 Correct 85 ms 73320 KB Output is correct
11 Correct 79 ms 75596 KB Output is correct
12 Correct 85 ms 69232 KB Output is correct
13 Correct 76 ms 81116 KB Output is correct
14 Correct 69 ms 71672 KB Output is correct
15 Correct 188 ms 81372 KB Output is correct
16 Correct 185 ms 80920 KB Output is correct
17 Correct 219 ms 82156 KB Output is correct
18 Correct 471 ms 87956 KB Output is correct
19 Incorrect 474 ms 85748 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 57944 KB Output is correct
2 Correct 10 ms 49692 KB Output is correct
3 Correct 10 ms 51800 KB Output is correct
4 Correct 8 ms 47708 KB Output is correct
5 Correct 6 ms 35420 KB Output is correct
6 Correct 10 ms 43868 KB Output is correct
7 Correct 9 ms 49752 KB Output is correct
8 Correct 10 ms 45916 KB Output is correct
9 Correct 10 ms 49932 KB Output is correct
10 Correct 92 ms 69840 KB Output is correct
11 Correct 85 ms 73320 KB Output is correct
12 Correct 79 ms 75596 KB Output is correct
13 Correct 85 ms 69232 KB Output is correct
14 Correct 76 ms 81116 KB Output is correct
15 Correct 69 ms 71672 KB Output is correct
16 Correct 188 ms 81372 KB Output is correct
17 Correct 185 ms 80920 KB Output is correct
18 Correct 219 ms 82156 KB Output is correct
19 Correct 471 ms 87956 KB Output is correct
20 Incorrect 474 ms 85748 KB Output isn't correct
21 Halted 0 ms 0 KB -