oj.uz

Submission #564394

# Submission time Handle Problem Language Result Execution time Memory
564394 2022-05-19T05:47:21 Z shahriarkhan Swapping Cities (APIO20_swap) C++14
6 / 100
 642 ms 131592 KB 
#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(sub[u]!=INF) 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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 3 ms 1492 KB Output is correct
6 Correct 2 ms 1364 KB Output is correct
7 Correct 2 ms 1492 KB Output is correct
8 Correct 2 ms 1492 KB Output is correct
9 Correct 230 ms 98720 KB Output is correct
10 Correct 276 ms 120820 KB Output is correct
11 Correct 250 ms 118596 KB Output is correct
12 Correct 292 ms 125632 KB Output is correct
13 Correct 319 ms 129476 KB Output is correct
14 Correct 236 ms 98652 KB Output is correct
15 Correct 398 ms 123092 KB Output is correct
16 Correct 403 ms 119664 KB Output is correct
17 Correct 438 ms 127160 KB Output is correct
18 Correct 617 ms 131040 KB Output is correct
19 Correct 105 ms 23824 KB Output is correct
20 Correct 357 ms 124016 KB Output is correct
21 Correct 395 ms 119144 KB Output is correct
22 Correct 398 ms 127616 KB Output is correct
23 Correct 626 ms 131592 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Incorrect 642 ms 127844 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 3 ms 1492 KB Output is correct
6 Correct 2 ms 1364 KB Output is correct
7 Correct 2 ms 1492 KB Output is correct
8 Correct 2 ms 1492 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Incorrect 3 ms 1460 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 3 ms 1492 KB Output is correct
7 Correct 2 ms 1364 KB Output is correct
8 Correct 2 ms 1492 KB Output is correct
9 Correct 2 ms 1492 KB Output is correct
10 Correct 230 ms 98720 KB Output is correct
11 Correct 276 ms 120820 KB Output is correct
12 Correct 250 ms 118596 KB Output is correct
13 Correct 292 ms 125632 KB Output is correct
14 Correct 319 ms 129476 KB Output is correct
15 Incorrect 3 ms 1460 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 3 ms 1492 KB Output is correct
6 Correct 2 ms 1364 KB Output is correct
7 Correct 2 ms 1492 KB Output is correct
8 Correct 2 ms 1492 KB Output is correct
9 Correct 230 ms 98720 KB Output is correct
10 Correct 276 ms 120820 KB Output is correct
11 Correct 250 ms 118596 KB Output is correct
12 Correct 292 ms 125632 KB Output is correct
13 Correct 319 ms 129476 KB Output is correct
14 Correct 236 ms 98652 KB Output is correct
15 Correct 398 ms 123092 KB Output is correct
16 Correct 403 ms 119664 KB Output is correct
17 Correct 438 ms 127160 KB Output is correct
18 Correct 617 ms 131040 KB Output is correct
19 Incorrect 642 ms 127844 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 3 ms 1492 KB Output is correct
7 Correct 2 ms 1364 KB Output is correct
8 Correct 2 ms 1492 KB Output is correct
9 Correct 2 ms 1492 KB Output is correct
10 Correct 230 ms 98720 KB Output is correct
11 Correct 276 ms 120820 KB Output is correct
12 Correct 250 ms 118596 KB Output is correct
13 Correct 292 ms 125632 KB Output is correct
14 Correct 319 ms 129476 KB Output is correct
15 Correct 236 ms 98652 KB Output is correct
16 Correct 398 ms 123092 KB Output is correct
17 Correct 403 ms 119664 KB Output is correct
18 Correct 438 ms 127160 KB Output is correct
19 Correct 617 ms 131040 KB Output is correct
20 Incorrect 642 ms 127844 KB Output isn't correct
21 Halted 0 ms 0 KB -