제출 #564218

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
564218		shahriarkhan	Swapping Cities (APIO20_swap)	C++14	6 / 100	669 ms	135396 KiB

swap

#include "swap.h"
#include<bits/stdc++.h>
using namespace std ;

const int LG = 30 , INF = 1e9 + 5 ;

struct query
{
    int u = 0 , v = 0 , w = 0 ;
};

bool cmp(query &a , query &b)
{
    return a.w < b.w ;
}

struct reachability_tree
{
    int cur = 0 , timer = 0 ;
    vector<vector<int> > adj , up , dp ;
    vector<int> tin , tout , par , swp , cost , vis , sub , edg ;
    void init(int n)
    {
        int siz = n + n + n ;
        adj = vector<vector<int> > (siz) ;
        up = vector<vector<int> > (siz , vector<int>(LG+1,0)) ;
        dp = vector<vector<int> > (siz , vector<int>(LG+1,0)) ;
        tin = vector<int> (siz , 0) ;
        tout = vector<int> (siz , 0) ;
        par = vector<int> (siz , 0) ;
        cost = vector<int> (siz , INF) ;
        vis = vector<int> (siz , 0) ;
        swp = vector<int> (siz , 0) ;
        sub = vector<int> (siz , INF) ;
        edg = vector<int> (siz , 0) ;
        for(int i = 1 ; i < siz ; ++i)
        {
            par[i] = i ;
        }
        cur = n + 1 ;
    }
    int find_root(int p)
    {
        if(par[p]==p) return p ;
        return par[p] = find_root(par[p]) ;
    }
    void union_edge(int u , int v , int cst)
    {
        int root_u = find_root(u) , root_v = find_root(v) ;

        if(root_u==root_v)
        {
            swp[root_u] = 1 , cost[root_u] = min(cost[root_u],cst) ;
            return ;
        }

        par[root_u] = cur , par[root_v] = cur ;

        adj[root_u].push_back(cur) ;
        adj[cur].push_back(root_u) ;
        adj[root_v].push_back(cur) ;
        adj[cur].push_back(root_v) ;

        edg[cur] = cst ;

        ++cur ;

    }

    void dfs(int s , int p)
    {
        if(vis[s]) return ;
        dp[s][0] = p , up[s][0] = max(swp[s],swp[p]) , tin[s] = ++timer , vis[s] = 1 , sub[s] = cost[s] ;
        for(int i = 1 ; i < LG ; ++i)
        {
            up[s][i] = max(up[s][i-1] , up[dp[s][i-1]][i-1]) ;
            dp[s][i] = dp[dp[s][i-1]][i-1] ;
        }
        for(int t : adj[s])
        {
            if(t==p) continue ;
            dfs(t,s) ;
            sub[s] = min(sub[s],sub[t]) ;
        }
        tout[s] = ++timer ;
    }

    int is_ancestor(int u , int v)
    {
        return ((tin[u]<=tin[v]) && (tout[u]>=tout[v])) ;
    }

    int find_ancestor(int u , int v)
    {
        if(is_ancestor(u,v)) return u ;
        if(is_ancestor(v,u)) return v ;
        for(int i = LG - 1 ; i >= 0 ; --i)
        {
            if(!is_ancestor(dp[u][i],v))
            {
                u = dp[u][i] ;
            }
        }
        return dp[u][0] ;
    }

    int find_nearest(int u)
    {
        if(swp[u]) return max(edg[u],sub[u]) ;
        int org_u = u ;
        for(int i = LG - 1 ; i >= 0 ; --i)
        {
            if(!up[u][i])
            {
                u = dp[u][i] ;
            }
        }
        return max(edg[org_u],sub[dp[u][0]]) ;
    }

    void process()
    {
        for(int i = 1 ; i <= cur ; ++i)
        {
            if(vis[i]) continue ;
            int root_i = find_root(i) ;
            dfs(root_i,root_i) ;
        }
    }

    int query(int x , int y)
    {
        ++x , ++y ;
        int lca = find_ancestor(x,y) ;
        int ret = find_nearest(lca) ;
        if(ret==INF) ret = -1 ;
        return ret ;
    }
} R ;

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W)
{
    R.init(N) ;
    vector<query> v ;
    for(int i = 0 ; i < M ; ++i)
    {
        v.push_back({U[i]+1,V[i]+1,W[i]}) ;
    }
    sort(v.begin(),v.end(),cmp) ;
    for(query q : v)
    {
        R.union_edge(q.u,q.v,q.w) ;
    }
    R.process() ;
}

int getMinimumFuelCapacity(int X, int Y)
{
    return R.query(X,Y) ;
}

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