제출 #1304691

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1304691		vtnoo	자매 도시 (APIO20_swap)	C++20	0 / 100	603 ms	589824 KiB

swap

//this is just a chatgpt try, is not my code
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e9+7;

int n, m;
int LOGG; // computed from n

// adjacency by arrays
struct Edge { int to, w, next; };
vector<Edge> edges;
vector<int> head; // head[u] index of first edge, -1 none
int edge_cnt;

// up and mx stored flat: up[a*LOGG + i]
vector<int> up_flat;
vector<int> mx_flat;

inline int UP(int a, int i){ return up_flat[a * LOGG + i]; }
inline void SET_UP(int a, int i, int v){ up_flat[a * LOGG + i] = v; }
inline int MX(int a, int i){ return mx_flat[a * LOGG + i]; }
inline void SET_MX(int a, int i, int v){ mx_flat[a * LOGG + i] = v; }

vector<int> dep;
vector<int> dp;

void add_edge(int u, int v, int w){
    edges[edge_cnt] = {v, w, head[u]};
    head[u] = edge_cnt++;
}

void dfs(int u, int p, int d){
    dep[u] = d;
    for(int ei = head[u]; ei != -1; ei = edges[ei].next){
        int v = edges[ei].to, c = edges[ei].w;
        if(v == p) continue;
        SET_UP(v, 0, u);
        SET_MX(v, 0, c);
        dfs(v, u, d+1);
    }
}

void dfs2(int u, int p){
    for(int ei = head[u]; ei != -1; ei = edges[ei].next){
        int v = edges[ei].to, c = edges[ei].w;
        if(v == p) continue;
        dfs2(v, u);
        dp[u] = min(dp[u], max(dp[v], c));
    }
}
void dfs3(int u, int p){
    for(int ei = head[u]; ei != -1; ei = edges[ei].next){
        int v = edges[ei].to, c = edges[ei].w;
        if(v == p) continue;
        dp[u] = min(dp[u], max(dp[v], c));
        dfs3(v, u);
    }
}

// jump a up by d, also compute max weight along jump if needed
int jump_node(int a, int d){
    for(int i = 0; d > 0; ++i){
        if(d & 1) a = UP(a, i);
        d >>= 1;
    }
    return a;
}

// return pair{node after jumping b up by k, maximum weight on that jump}
pair<int,int> jump_with_max(int a, int k){
    int best = 0;
    for(int i = 0; k; ++i){
        if(k & 1){
            best = max(best, MX(a, i));
            a = UP(a, i);
        }
        k >>= 1;
    }
    return {a, best};
}

// LCA-like: return maximum edge weight along path between a and b
int path_max_between(int a, int b){
    if(a == b) return 0;
    int ans = 0;
    if(dep[a] < dep[b]) swap(a,b); // ensure a deeper
    int diff = dep[a] - dep[b];
    // lift a up
    for(int i = 0; i < LOGG; ++i){
        if(diff & (1<<i)){
            ans = max(ans, MX(a, i));
            a = UP(a, i);
        }
    }
    if(a == b) return ans;
    for(int i = LOGG-1; i >= 0; --i){
        if(UP(a,i) != UP(b,i)){
            ans = max(ans, MX(a,i));
            ans = max(ans, MX(b,i));
            a = UP(a,i);
            b = UP(b,i);
        }
    }
    // now a and b are children of LCA
    ans = max(ans, MX(a,0));
    ans = max(ans, MX(b,0));
    return ans;
}

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n = N; m = M;
    // compute LOGG precisely
    LOGG = 1;
    while((1<<LOGG) <= n) ++LOGG;
    LOGG += 1; // a bit of margin

    // allocate adjacency arrays
    head.assign(n, -1);
    edges.resize(2 * m);
    edge_cnt = 0;

    for(int i = 0; i < m; ++i){
        int u = U[i], v = V[i], w = W[i];
        add_edge(u, v, w);
        add_edge(v, u, w);
    }

    // allocate up/mx flat arrays
    up_flat.assign(n * LOGG, 0);
    mx_flat.assign(n * LOGG, 0);

    dep.assign(n, 0);
    dp.assign(n, INF);

    // initialize root 0
    SET_UP(0, 0, 0);
    SET_MX(0, 0, 0);
    dfs(0, 0, 0);

    // build binary lifting tables
    for(int j = 1; j < LOGG; ++j){
        for(int v = 0; v < n; ++v){
            int mid = UP(v, j-1);
            SET_UP(v, j, UP(mid, j-1));
            SET_MX(v, j, max(MX(v, j-1), MX(mid, j-1)));
        }
    }

    // compute dp initial (third smallest incident edge weight)
    for(int u = 0; u < n; ++u){
        int best1 = INF, best2 = INF, best3 = INF;
        for(int ei = head[u]; ei != -1; ei = edges[ei].next){
            int c = edges[ei].w;
            if(c < best1){
                best3 = best2;
                best2 = best1;
                best1 = c;
            } else if(c < best2){
                best3 = best2;
                best2 = c;
            } else if(c < best3){
                best3 = c;
            }
        }
        dp[u] = best3;
    }

    dfs2(0, 0);
    dfs3(0, 0);
}

int getMinimumFuelCapacity(int X, int Y) {
    int pathMax = path_max_between(X, Y);
    if(dp[X] == INF) return -1;
    return max(pathMax, dp[X]);
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27