oj.uz

답안 #1069224

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1069224 2024-08-21T17:46:38 Z TVSown 자매 도시 (APIO20_swap) C++17
0 / 100
 486 ms 47300 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 = 3e5 + 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;
    if(lift(p, l) >= nn) 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
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 8952 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 3 ms 9052 KB Output is correct
5 Correct 3 ms 9056 KB Output is correct
6 Correct 2 ms 9064 KB Output is correct
7 Correct 2 ms 9052 KB Output is correct
8 Correct 2 ms 9052 KB Output is correct
9 Correct 53 ms 32924 KB Output is correct
10 Correct 65 ms 38236 KB Output is correct
11 Correct 64 ms 37712 KB Output is correct
12 Correct 81 ms 39504 KB Output is correct
13 Correct 64 ms 42576 KB Output is correct
14 Correct 85 ms 33104 KB Output is correct
15 Correct 187 ms 42472 KB Output is correct
16 Correct 197 ms 40380 KB Output is correct
17 Correct 219 ms 42196 KB Output is correct
18 Correct 472 ms 45492 KB Output is correct
19 Incorrect 101 ms 17548 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 8952 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Incorrect 486 ms 47300 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 8952 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 3 ms 9052 KB Output is correct
5 Correct 3 ms 9056 KB Output is correct
6 Correct 2 ms 9064 KB Output is correct
7 Correct 2 ms 9052 KB Output is correct
8 Correct 2 ms 9052 KB Output is correct
9 Incorrect 2 ms 8792 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 8792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 8952 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 3 ms 9052 KB Output is correct
5 Correct 3 ms 9056 KB Output is correct
6 Correct 2 ms 9064 KB Output is correct
7 Correct 2 ms 9052 KB Output is correct
8 Correct 2 ms 9052 KB Output is correct
9 Correct 53 ms 32924 KB Output is correct
10 Correct 65 ms 38236 KB Output is correct
11 Correct 64 ms 37712 KB Output is correct
12 Correct 81 ms 39504 KB Output is correct
13 Correct 64 ms 42576 KB Output is correct
14 Correct 85 ms 33104 KB Output is correct
15 Correct 187 ms 42472 KB Output is correct
16 Correct 197 ms 40380 KB Output is correct
17 Correct 219 ms 42196 KB Output is correct
18 Correct 472 ms 45492 KB Output is correct
19 Incorrect 486 ms 47300 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 8792 KB Output isn't correct
2 Halted 0 ms 0 KB -