oj.uz

답안 #1069221

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1069221 2024-08-21T17:43:12 Z TVSown 자매 도시 (APIO20_swap) C++17
0 / 100
 371 ms 524288 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;
    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, w = e[i].w;

        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]];
        }
    }
}

Compilation message

swap.cpp: In function 'void Union(int, int)':
swap.cpp:42:7: warning: operation on 'n' may be undefined [-Wsequence-point]
   42 |     p[++n] = n;
      |       ^~~
swap.cpp:42:7: warning: operation on 'n' may be undefined [-Wsequence-point]
swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:121:37: warning: unused variable 'w' [-Wunused-variable]
  121 |         int u = e[i].u, v = e[i].v, w = e[i].w;
      |                                     ^

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Runtime error 326 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Runtime error 371 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Runtime error 326 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Runtime error 326 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Runtime error 326 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Runtime error 326 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -