oj.uz

Submission #564400

# Submission time Handle Problem Language Result Execution time Memory
564400 2022-05-19T06:23:10 Z shahriarkhan Swapping Cities (APIO20_swap) C++14
36 / 100
 658 ms 126224 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 , edg , deg ;
    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) ;
        swp = vector<int> (siz , 0) ;
        edg = vector<int> (siz , 0) ;
        deg = 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)
    {
        ++deg[u] , ++deg[v] ;
        if((deg[u]>=3) || (deg[v]>=3)) swp[cur] = 1 ;
        int root_u = find_root(u) , root_v = find_root(v) ;

        swp[cur] |= (swp[root_u]|swp[root_v]) ;

        adj[cur].push_back(root_u) ;

        if(root_u!=root_v) adj[cur].push_back(root_v) ;
        else swp[cur] = 1 ;

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

        edg[cur] = cst ;

        ++cur ;

    }

    void dfs(int s , int p)
    {
        dp[s][0] = p , up[s][0] = max(swp[s],swp[p]) , tin[s] = ++timer ;
        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) ;
        }
        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 edg[u] ;
        int org_u = u ;
        for(int i = LG - 1 ; i >= 0 ; --i)
        {
            if(!up[u][i])
            {
                u = dp[u][i] ;
            }
        }
        if(!swp[dp[u][0]]) return -1 ;
        return edg[dp[u][0]] ;
    }

    void process()
    {
        int root_1 = find_root(1) ;
        dfs(root_1,root_1) ;
    }

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

Compilation message

swap.cpp: In member function 'int reachability_tree::find_nearest(int)':
swap.cpp:105:13: warning: unused variable 'org_u' [-Wunused-variable]
  105 |         int org_u = u ;
      |             ^~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 2 ms 1364 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 195 ms 94904 KB Output is correct
10 Correct 235 ms 115992 KB Output is correct
11 Correct 227 ms 114000 KB Output is correct
12 Correct 259 ms 120756 KB Output is correct
13 Correct 300 ms 122780 KB Output is correct
14 Correct 215 ms 94792 KB Output is correct
15 Correct 360 ms 118408 KB Output is correct
16 Correct 369 ms 115280 KB Output is correct
17 Correct 392 ms 122324 KB Output is correct
18 Correct 594 ms 124368 KB Output is correct
19 Correct 122 ms 22588 KB Output is correct
20 Correct 362 ms 119324 KB Output is correct
21 Correct 354 ms 114672 KB Output is correct
22 Correct 385 ms 122772 KB Output is correct
23 Correct 658 ms 124720 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 509 ms 120000 KB Output is correct
4 Correct 519 ms 126224 KB Output is correct
5 Correct 521 ms 122004 KB Output is correct
6 Correct 514 ms 125688 KB Output is correct
7 Correct 537 ms 123952 KB Output is correct
8 Correct 507 ms 118816 KB Output is correct
9 Correct 547 ms 123280 KB Output is correct
10 Correct 517 ms 117660 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 2 ms 1364 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 Correct 2 ms 1492 KB Output is correct
11 Correct 2 ms 1492 KB Output is correct
12 Correct 2 ms 1364 KB Output is correct
13 Correct 2 ms 1236 KB Output is correct
14 Correct 2 ms 1236 KB Output is correct
15 Correct 2 ms 1492 KB Output is correct
16 Correct 2 ms 1492 KB Output is correct
17 Correct 2 ms 1492 KB Output is correct
18 Correct 3 ms 1376 KB Output is correct
19 Correct 2 ms 1108 KB Output is correct
20 Correct 3 ms 1492 KB Output is correct
21 Correct 2 ms 1364 KB Output is correct
22 Runtime error 2 ms 1108 KB Execution killed with signal 11
23 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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 2 ms 1364 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 195 ms 94904 KB Output is correct
11 Correct 235 ms 115992 KB Output is correct
12 Correct 227 ms 114000 KB Output is correct
13 Correct 259 ms 120756 KB Output is correct
14 Correct 300 ms 122780 KB Output is correct
15 Correct 2 ms 1492 KB Output is correct
16 Correct 2 ms 1492 KB Output is correct
17 Correct 2 ms 1364 KB Output is correct
18 Correct 2 ms 1236 KB Output is correct
19 Correct 2 ms 1236 KB Output is correct
20 Correct 2 ms 1492 KB Output is correct
21 Correct 2 ms 1492 KB Output is correct
22 Correct 2 ms 1492 KB Output is correct
23 Correct 3 ms 1376 KB Output is correct
24 Correct 2 ms 1108 KB Output is correct
25 Correct 3 ms 1492 KB Output is correct
26 Correct 2 ms 1364 KB Output is correct
27 Runtime error 2 ms 1108 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 2 ms 1364 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 195 ms 94904 KB Output is correct
10 Correct 235 ms 115992 KB Output is correct
11 Correct 227 ms 114000 KB Output is correct
12 Correct 259 ms 120756 KB Output is correct
13 Correct 300 ms 122780 KB Output is correct
14 Correct 215 ms 94792 KB Output is correct
15 Correct 360 ms 118408 KB Output is correct
16 Correct 369 ms 115280 KB Output is correct
17 Correct 392 ms 122324 KB Output is correct
18 Correct 594 ms 124368 KB Output is correct
19 Correct 509 ms 120000 KB Output is correct
20 Correct 519 ms 126224 KB Output is correct
21 Correct 521 ms 122004 KB Output is correct
22 Correct 514 ms 125688 KB Output is correct
23 Correct 537 ms 123952 KB Output is correct
24 Correct 507 ms 118816 KB Output is correct
25 Correct 547 ms 123280 KB Output is correct
26 Correct 517 ms 117660 KB Output is correct
27 Correct 2 ms 1492 KB Output is correct
28 Correct 2 ms 1492 KB Output is correct
29 Correct 2 ms 1364 KB Output is correct
30 Correct 2 ms 1236 KB Output is correct
31 Correct 2 ms 1236 KB Output is correct
32 Correct 2 ms 1492 KB Output is correct
33 Correct 2 ms 1492 KB Output is correct
34 Correct 2 ms 1492 KB Output is correct
35 Correct 3 ms 1376 KB Output is correct
36 Correct 28 ms 16664 KB Output is correct
37 Correct 252 ms 120776 KB Output is correct
38 Correct 257 ms 120760 KB Output is correct
39 Correct 259 ms 120664 KB Output is correct
40 Correct 262 ms 119108 KB Output is correct
41 Correct 240 ms 118508 KB Output is correct
42 Correct 240 ms 108608 KB Output is correct
43 Correct 247 ms 120860 KB Output is correct
44 Correct 258 ms 120760 KB Output is correct
45 Correct 296 ms 123304 KB Output is correct
46 Correct 268 ms 120768 KB Output is correct
47 Correct 33 ms 15356 KB Output is correct
48 Correct 353 ms 122376 KB Output is correct
49 Correct 350 ms 122300 KB Output is correct
50 Correct 370 ms 122068 KB Output is correct
51 Correct 366 ms 121536 KB Output is correct
52 Correct 340 ms 114288 KB Output is correct
53 Correct 282 ms 82748 KB Output is correct
54 Correct 366 ms 122880 KB Output is correct
55 Correct 351 ms 122412 KB Output is correct
56 Correct 554 ms 124492 KB Output is correct
57 Correct 389 ms 122936 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 2 ms 1364 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 195 ms 94904 KB Output is correct
11 Correct 235 ms 115992 KB Output is correct
12 Correct 227 ms 114000 KB Output is correct
13 Correct 259 ms 120756 KB Output is correct
14 Correct 300 ms 122780 KB Output is correct
15 Correct 215 ms 94792 KB Output is correct
16 Correct 360 ms 118408 KB Output is correct
17 Correct 369 ms 115280 KB Output is correct
18 Correct 392 ms 122324 KB Output is correct
19 Correct 594 ms 124368 KB Output is correct
20 Correct 509 ms 120000 KB Output is correct
21 Correct 519 ms 126224 KB Output is correct
22 Correct 521 ms 122004 KB Output is correct
23 Correct 514 ms 125688 KB Output is correct
24 Correct 537 ms 123952 KB Output is correct
25 Correct 507 ms 118816 KB Output is correct
26 Correct 547 ms 123280 KB Output is correct
27 Correct 517 ms 117660 KB Output is correct
28 Correct 2 ms 1492 KB Output is correct
29 Correct 2 ms 1492 KB Output is correct
30 Correct 2 ms 1364 KB Output is correct
31 Correct 2 ms 1236 KB Output is correct
32 Correct 2 ms 1236 KB Output is correct
33 Correct 2 ms 1492 KB Output is correct
34 Correct 2 ms 1492 KB Output is correct
35 Correct 2 ms 1492 KB Output is correct
36 Correct 3 ms 1376 KB Output is correct
37 Correct 28 ms 16664 KB Output is correct
38 Correct 252 ms 120776 KB Output is correct
39 Correct 257 ms 120760 KB Output is correct
40 Correct 259 ms 120664 KB Output is correct
41 Correct 262 ms 119108 KB Output is correct
42 Correct 240 ms 118508 KB Output is correct
43 Correct 240 ms 108608 KB Output is correct
44 Correct 247 ms 120860 KB Output is correct
45 Correct 258 ms 120760 KB Output is correct
46 Correct 296 ms 123304 KB Output is correct
47 Correct 268 ms 120768 KB Output is correct
48 Correct 33 ms 15356 KB Output is correct
49 Correct 353 ms 122376 KB Output is correct
50 Correct 350 ms 122300 KB Output is correct
51 Correct 370 ms 122068 KB Output is correct
52 Correct 366 ms 121536 KB Output is correct
53 Correct 340 ms 114288 KB Output is correct
54 Correct 282 ms 82748 KB Output is correct
55 Correct 366 ms 122880 KB Output is correct
56 Correct 351 ms 122412 KB Output is correct
57 Correct 554 ms 124492 KB Output is correct
58 Correct 389 ms 122936 KB Output is correct
59 Correct 122 ms 22588 KB Output is correct
60 Correct 362 ms 119324 KB Output is correct
61 Correct 354 ms 114672 KB Output is correct
62 Correct 385 ms 122772 KB Output is correct
63 Correct 658 ms 124720 KB Output is correct
64 Correct 2 ms 1108 KB Output is correct
65 Correct 3 ms 1492 KB Output is correct
66 Correct 2 ms 1364 KB Output is correct
67 Runtime error 2 ms 1108 KB Execution killed with signal 11
68 Halted 0 ms 0 KB -