oj.uz

Submission #564218

# Submission time Handle Problem Language Result Execution time Memory
564218 2022-05-18T18:26:27 Z shahriarkhan Swapping Cities (APIO20_swap) C++14
6 / 100
 669 ms 135396 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(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.0 / 6.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 212 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 2 ms 1492 KB Output is correct
6 Correct 2 ms 1336 KB Output is correct
7 Correct 2 ms 1492 KB Output is correct
8 Correct 3 ms 1492 KB Output is correct
9 Correct 228 ms 99888 KB Output is correct
10 Correct 270 ms 122224 KB Output is correct
11 Correct 251 ms 120132 KB Output is correct
12 Correct 267 ms 127268 KB Output is correct
13 Correct 337 ms 131188 KB Output is correct
14 Correct 218 ms 100024 KB Output is correct
15 Correct 412 ms 126972 KB Output is correct
16 Correct 415 ms 123504 KB Output is correct
17 Correct 400 ms 131136 KB Output is correct
18 Correct 610 ms 134980 KB Output is correct
19 Correct 113 ms 25292 KB Output is correct
20 Correct 377 ms 127792 KB Output is correct
21 Correct 395 ms 122976 KB Output is correct
22 Correct 399 ms 131520 KB Output is correct
23 Correct 669 ms 135396 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 212 KB Output is correct
3 Incorrect 624 ms 131116 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 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 2 ms 1492 KB Output is correct
6 Correct 2 ms 1336 KB Output is correct
7 Correct 2 ms 1492 KB Output is correct
8 Correct 3 ms 1492 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Incorrect 2 ms 1492 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 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 2 ms 1492 KB Output is correct
7 Correct 2 ms 1336 KB Output is correct
8 Correct 2 ms 1492 KB Output is correct
9 Correct 3 ms 1492 KB Output is correct
10 Correct 228 ms 99888 KB Output is correct
11 Correct 270 ms 122224 KB Output is correct
12 Correct 251 ms 120132 KB Output is correct
13 Correct 267 ms 127268 KB Output is correct
14 Correct 337 ms 131188 KB Output is correct
15 Incorrect 2 ms 1492 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 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 2 ms 1492 KB Output is correct
6 Correct 2 ms 1336 KB Output is correct
7 Correct 2 ms 1492 KB Output is correct
8 Correct 3 ms 1492 KB Output is correct
9 Correct 228 ms 99888 KB Output is correct
10 Correct 270 ms 122224 KB Output is correct
11 Correct 251 ms 120132 KB Output is correct
12 Correct 267 ms 127268 KB Output is correct
13 Correct 337 ms 131188 KB Output is correct
14 Correct 218 ms 100024 KB Output is correct
15 Correct 412 ms 126972 KB Output is correct
16 Correct 415 ms 123504 KB Output is correct
17 Correct 400 ms 131136 KB Output is correct
18 Correct 610 ms 134980 KB Output is correct
19 Incorrect 624 ms 131116 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 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 2 ms 1492 KB Output is correct
7 Correct 2 ms 1336 KB Output is correct
8 Correct 2 ms 1492 KB Output is correct
9 Correct 3 ms 1492 KB Output is correct
10 Correct 228 ms 99888 KB Output is correct
11 Correct 270 ms 122224 KB Output is correct
12 Correct 251 ms 120132 KB Output is correct
13 Correct 267 ms 127268 KB Output is correct
14 Correct 337 ms 131188 KB Output is correct
15 Correct 218 ms 100024 KB Output is correct
16 Correct 412 ms 126972 KB Output is correct
17 Correct 415 ms 123504 KB Output is correct
18 Correct 400 ms 131136 KB Output is correct
19 Correct 610 ms 134980 KB Output is correct
20 Incorrect 624 ms 131116 KB Output isn't correct
21 Halted 0 ms 0 KB -