oj.uz

Submission #466005

# Submission time Handle Problem Language Result Execution time Memory
466005 2021-08-17T14:00:52 Z alextodoran Swapping Cities (APIO20_swap) C++17
100 / 100
 873 ms 53088 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>
#include "swap.h"

using namespace std;

typedef long long ll;

const int INF = INT_MAX / 2;

struct Edge
{
    int u, v;
    int w;

    int other (int x)
    {
        return (u ^ v ^ x);
    }

    bool primary;
};

int N, M;

vector <Edge> edges;

vector <vector <Edge*>> adj;

vector <int> special;
vector <int> cost;

vector <int> parent;
vector <int> parw;
vector <int> depth;

int BITS;

vector <vector <int>> anc;
vector <vector <int>> ancw;

int ancestor (int &u, int k)
{
    int maxw = 0;
    for(int bit = BITS - 1; bit >= 0; bit--)
        if((k >> bit) & 1)
        {
            maxw = max(maxw, ancw[u][bit]);
            u = anc[u][bit];
        }
    return maxw;
}

int dist (int u, int v)
{
    int maxw = 0;
    if(depth[u] > depth[v])
        maxw = max(maxw, ancestor(u, depth[u] - depth[v]));
    if(depth[v] > depth[u])
        maxw = max(maxw, ancestor(v, depth[v] - depth[u]));

    if(u == v)
        return maxw;

    for(int bit = BITS - 1; bit >= 0; bit--)
        if(anc[u][bit] != anc[v][bit])
        {
            maxw = max(maxw, ancw[u][bit]);
            maxw = max(maxw, ancw[v][bit]);
            u = anc[u][bit];
            v = anc[v][bit];
        }
    maxw = max(maxw, parw[u]);
    maxw = max(maxw, parw[v]);

    return maxw;
}

void init (int _N, int _M, vector <int> U, vector <int> V, vector <int> W)
{
    N = _N;
    M = _M;

    /// Process edges

    edges = vector <Edge> (M);
    for(int i = 0; i < M; i++)
        edges[i] = Edge{U[i], V[i], W[i], false};

    adj = vector <vector <Edge*>> (N);
    for(int i = 0; i < M; i++)
    {
        adj[edges[i].u].push_back(&edges[i]);
        adj[edges[i].v].push_back(&edges[i]);
    }

    /// Use DSU to find minimum spanning tree

    {
        vector <int> par (N);
        for(int u = 0; u < N; u++)
            par[u] = u;

        function <int (int)> findRoot = [&] (int u)
        {
            if(par[u] == u)
                return u;
            return par[u] = findRoot(par[u]);
        };
        function <bool (int, int)> join = [&] (int u, int v)
        {
            u = findRoot(u);
            v = findRoot(v);

            if(u == v)
                return false;

            par[u] = v;
            return true;
        };

        // Sort edges by weight

        vector <int> edgeOrder (M);
        for(int i = 0; i < M; i++)
            edgeOrder[i] = i;
        sort(edgeOrder.begin(), edgeOrder.end(),
             [&] (const int &x, const int &y)
             {
                 return edges[x].w < edges[y].w;
             });

        // Find "primary" edges that form the spanning tree

        for(int j = 0; j < M; j++)
        {
            int i = edgeOrder[j];
            if(join(edges[i].u, edges[i].v) == true)
                edges[i].primary = true;
        }
    }

    /// Use DFS to find the structure of the tree

    parent = vector <int> (N, -1);
    parw = vector <int> (N, 0);
    depth = vector <int> (N, 0);

    vector <bool> visited (N, false);

    function <void (int)> dfs = [&] (int u)
    {
        visited[u] = true;
        for(Edge* e : adj[u])
            if(e->primary == true)
            {
                int v = e->other(u);
                if(visited[v] == false)
                {
                    depth[v] = depth[u] + 1;
                    parent[v] = u;
                    parw[v] = e->w;

                    dfs(v);
                }
            }
    };

    for(int u = 0; u < N; u++)
        if(visited[u] == false)
            dfs(u);

    /// Use binary lifting to get ancestors and be able to compute distance

    BITS = 0;
    while((1 << BITS) <= N)
        BITS++;

    anc = vector <vector <int>> (N, vector <int> (BITS, -1));
    ancw = vector <vector <int>> (N, vector <int> (BITS, 0));

    for(int u = 0; u < N; u++)
    {
        anc[u][0] = parent[u];
        ancw[u][0] = parw[u];
    }
    for(int bit = 1; bit < BITS; bit++)
        for(int u = 0; u < N; u++)
        {
            if(anc[u][bit - 1] != -1)
            {
                anc[u][bit] = anc[anc[u][bit - 1]][bit - 1];
                ancw[u][bit] = max(ancw[u][bit - 1], ancw[anc[u][bit - 1]][bit - 1]);
            }
        }

    /// Find special cost for each node

    // Intersection nodes

    special = vector <int> (N, INF);
    for(int u = 0; u < N; u++)
        if((int) adj[u].size() >= 3)
        {
            vector <int> aux;
            for(Edge* e : adj[u])
                aux.push_back(e->w);
            sort(aux.begin(), aux.end());

            special[u] = aux[2];
        }

    // Cycle nodes

    for(int i = 0; i < M; i++)
        if(edges[i].primary == false)
            special[edges[i].u] = min(special[edges[i].u], edges[i].w);

    /// Use DSU to find additional cost for each node

    {
        vector <int> par (N);
        for(int u = 0; u < N; u++)
            par[u] = u;
        vector <int> wpar (N, INF);
        vector <int> dim (N, 1);
        vector <int> minCost (N, INF);

        function <int (int)> findRoot = [&] (int u)
        {
            if(par[u] == u)
                return u;
            return findRoot(par[u]);
        };
        function <void (int, int, int)> join = [&] (int u, int v, int w)
        {
            u = findRoot(u);
            v = findRoot(v);

            if(u == v)
                return;

            if(dim[u] > dim[v])
                swap(u, v);

            par[u] = v;
            wpar[u] = w;
            dim[v] += dim[u];
            if(minCost[v] == INF && minCost[u] != INF)
                minCost[v] = w;
        };

        vector <int> edgeOrder (M);
        for(int i = 0; i < M; i++)
            edgeOrder[i] = i;
        sort(edgeOrder.begin(), edgeOrder.end(),
             [&] (const int &x, const int &y)
             {
                 return edges[x].w < edges[y].w;
             });

        vector <int> specialOrder (N);
        for(int u = 0; u < N; u++)
            specialOrder[u] = u;
        sort(specialOrder.begin(), specialOrder.end(),
             [&] (const int &u, const int &v)
             {
                 return special[u] < special[v];
             });

        int currEdge = 0;
        int currSpecial = 0;

        while(currEdge < M || currSpecial < N)
        {
            if(currSpecial == N || (currEdge < M
               && edges[edgeOrder[currEdge]].w
                < special[specialOrder[currSpecial]]))
            {
                int i = edgeOrder[currEdge];
                join(edges[i].u, edges[i].v, edges[i].w);

                currEdge++;
            }
            else
            {
                int u = specialOrder[currSpecial];
                int r = findRoot(u);
                if(minCost[r] == INF)
                    minCost[r] = special[u];

                currSpecial++;
            }
        }

        cost = vector <int> (N);

        for(int u = 0; u < N; u++)
        {
            cost[u] = minCost[u];

            int v = u;
            int maxw = 0;
            while(par[v] != v)
            {
                maxw = max(maxw, wpar[v]);
                v = par[v];
                cost[u] = min(cost[u], max(maxw, minCost[v]));
            }
        }
    }
}

int getMinimumFuelCapacity (int U, int V)
{
    int answer = max(dist(U, V), cost[U]);
    if(answer == INF)
        return -1;
    return answer;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 186 ms 30680 KB Output is correct
10 Correct 231 ms 38900 KB Output is correct
11 Correct 254 ms 37716 KB Output is correct
12 Correct 240 ms 40348 KB Output is correct
13 Correct 231 ms 42028 KB Output is correct
14 Correct 209 ms 30172 KB Output is correct
15 Correct 596 ms 40532 KB Output is correct
16 Correct 599 ms 37776 KB Output is correct
17 Correct 627 ms 43560 KB Output is correct
18 Correct 625 ms 42140 KB Output is correct
19 Correct 123 ms 9800 KB Output is correct
20 Correct 671 ms 40476 KB Output is correct
21 Correct 671 ms 38372 KB Output is correct
22 Correct 646 ms 42060 KB Output is correct
23 Correct 628 ms 42632 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 228 ms 35492 KB Output is correct
4 Correct 234 ms 37176 KB Output is correct
5 Correct 240 ms 36144 KB Output is correct
6 Correct 230 ms 37020 KB Output is correct
7 Correct 240 ms 36624 KB Output is correct
8 Correct 229 ms 35272 KB Output is correct
9 Correct 230 ms 36436 KB Output is correct
10 Correct 231 ms 34860 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 2 ms 588 KB Output is correct
17 Correct 1 ms 588 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 2 ms 460 KB Output is correct
20 Correct 2 ms 588 KB Output is correct
21 Correct 2 ms 460 KB Output is correct
22 Correct 2 ms 332 KB Output is correct
23 Correct 1 ms 460 KB Output is correct
24 Correct 3 ms 684 KB Output is correct
25 Correct 3 ms 588 KB Output is correct
26 Correct 3 ms 588 KB Output is correct
27 Correct 2 ms 588 KB Output is correct
28 Correct 3 ms 588 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 186 ms 30680 KB Output is correct
11 Correct 231 ms 38900 KB Output is correct
12 Correct 254 ms 37716 KB Output is correct
13 Correct 240 ms 40348 KB Output is correct
14 Correct 231 ms 42028 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 2 ms 588 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 2 ms 588 KB Output is correct
22 Correct 1 ms 588 KB Output is correct
23 Correct 2 ms 460 KB Output is correct
24 Correct 2 ms 460 KB Output is correct
25 Correct 2 ms 588 KB Output is correct
26 Correct 2 ms 460 KB Output is correct
27 Correct 2 ms 332 KB Output is correct
28 Correct 1 ms 460 KB Output is correct
29 Correct 3 ms 684 KB Output is correct
30 Correct 3 ms 588 KB Output is correct
31 Correct 3 ms 588 KB Output is correct
32 Correct 2 ms 588 KB Output is correct
33 Correct 3 ms 588 KB Output is correct
34 Correct 21 ms 4544 KB Output is correct
35 Correct 249 ms 39788 KB Output is correct
36 Correct 255 ms 37144 KB Output is correct
37 Correct 220 ms 35396 KB Output is correct
38 Correct 215 ms 34328 KB Output is correct
39 Correct 215 ms 33860 KB Output is correct
40 Correct 176 ms 31224 KB Output is correct
41 Correct 251 ms 37936 KB Output is correct
42 Correct 274 ms 39084 KB Output is correct
43 Correct 247 ms 40300 KB Output is correct
44 Correct 209 ms 34868 KB Output is correct
45 Correct 284 ms 35280 KB Output is correct
46 Correct 247 ms 37976 KB Output is correct
47 Correct 208 ms 36136 KB Output is correct
48 Correct 203 ms 36492 KB Output is correct
49 Correct 133 ms 14844 KB Output is correct
50 Correct 111 ms 12488 KB Output is correct
51 Correct 220 ms 29456 KB Output is correct
52 Correct 366 ms 44228 KB Output is correct
53 Correct 296 ms 44000 KB Output is correct
54 Correct 430 ms 49292 KB Output is correct
55 Correct 257 ms 43552 KB Output is correct
56 Correct 326 ms 43544 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 186 ms 30680 KB Output is correct
10 Correct 231 ms 38900 KB Output is correct
11 Correct 254 ms 37716 KB Output is correct
12 Correct 240 ms 40348 KB Output is correct
13 Correct 231 ms 42028 KB Output is correct
14 Correct 209 ms 30172 KB Output is correct
15 Correct 596 ms 40532 KB Output is correct
16 Correct 599 ms 37776 KB Output is correct
17 Correct 627 ms 43560 KB Output is correct
18 Correct 625 ms 42140 KB Output is correct
19 Correct 228 ms 35492 KB Output is correct
20 Correct 234 ms 37176 KB Output is correct
21 Correct 240 ms 36144 KB Output is correct
22 Correct 230 ms 37020 KB Output is correct
23 Correct 240 ms 36624 KB Output is correct
24 Correct 229 ms 35272 KB Output is correct
25 Correct 230 ms 36436 KB Output is correct
26 Correct 231 ms 34860 KB Output is correct
27 Correct 2 ms 460 KB Output is correct
28 Correct 2 ms 588 KB Output is correct
29 Correct 1 ms 460 KB Output is correct
30 Correct 1 ms 460 KB Output is correct
31 Correct 1 ms 460 KB Output is correct
32 Correct 1 ms 460 KB Output is correct
33 Correct 2 ms 588 KB Output is correct
34 Correct 1 ms 588 KB Output is correct
35 Correct 2 ms 460 KB Output is correct
36 Correct 21 ms 4544 KB Output is correct
37 Correct 249 ms 39788 KB Output is correct
38 Correct 255 ms 37144 KB Output is correct
39 Correct 220 ms 35396 KB Output is correct
40 Correct 215 ms 34328 KB Output is correct
41 Correct 215 ms 33860 KB Output is correct
42 Correct 176 ms 31224 KB Output is correct
43 Correct 251 ms 37936 KB Output is correct
44 Correct 274 ms 39084 KB Output is correct
45 Correct 247 ms 40300 KB Output is correct
46 Correct 209 ms 34868 KB Output is correct
47 Correct 34 ms 4512 KB Output is correct
48 Correct 634 ms 39780 KB Output is correct
49 Correct 642 ms 38240 KB Output is correct
50 Correct 634 ms 36980 KB Output is correct
51 Correct 515 ms 36524 KB Output is correct
52 Correct 451 ms 34108 KB Output is correct
53 Correct 319 ms 25904 KB Output is correct
54 Correct 663 ms 39480 KB Output is correct
55 Correct 625 ms 40216 KB Output is correct
56 Correct 563 ms 42792 KB Output is correct
57 Correct 435 ms 37248 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 186 ms 30680 KB Output is correct
11 Correct 231 ms 38900 KB Output is correct
12 Correct 254 ms 37716 KB Output is correct
13 Correct 240 ms 40348 KB Output is correct
14 Correct 231 ms 42028 KB Output is correct
15 Correct 209 ms 30172 KB Output is correct
16 Correct 596 ms 40532 KB Output is correct
17 Correct 599 ms 37776 KB Output is correct
18 Correct 627 ms 43560 KB Output is correct
19 Correct 625 ms 42140 KB Output is correct
20 Correct 228 ms 35492 KB Output is correct
21 Correct 234 ms 37176 KB Output is correct
22 Correct 240 ms 36144 KB Output is correct
23 Correct 230 ms 37020 KB Output is correct
24 Correct 240 ms 36624 KB Output is correct
25 Correct 229 ms 35272 KB Output is correct
26 Correct 230 ms 36436 KB Output is correct
27 Correct 231 ms 34860 KB Output is correct
28 Correct 2 ms 460 KB Output is correct
29 Correct 2 ms 588 KB Output is correct
30 Correct 1 ms 460 KB Output is correct
31 Correct 1 ms 460 KB Output is correct
32 Correct 1 ms 460 KB Output is correct
33 Correct 1 ms 460 KB Output is correct
34 Correct 2 ms 588 KB Output is correct
35 Correct 1 ms 588 KB Output is correct
36 Correct 2 ms 460 KB Output is correct
37 Correct 21 ms 4544 KB Output is correct
38 Correct 249 ms 39788 KB Output is correct
39 Correct 255 ms 37144 KB Output is correct
40 Correct 220 ms 35396 KB Output is correct
41 Correct 215 ms 34328 KB Output is correct
42 Correct 215 ms 33860 KB Output is correct
43 Correct 176 ms 31224 KB Output is correct
44 Correct 251 ms 37936 KB Output is correct
45 Correct 274 ms 39084 KB Output is correct
46 Correct 247 ms 40300 KB Output is correct
47 Correct 209 ms 34868 KB Output is correct
48 Correct 34 ms 4512 KB Output is correct
49 Correct 634 ms 39780 KB Output is correct
50 Correct 642 ms 38240 KB Output is correct
51 Correct 634 ms 36980 KB Output is correct
52 Correct 515 ms 36524 KB Output is correct
53 Correct 451 ms 34108 KB Output is correct
54 Correct 319 ms 25904 KB Output is correct
55 Correct 663 ms 39480 KB Output is correct
56 Correct 625 ms 40216 KB Output is correct
57 Correct 563 ms 42792 KB Output is correct
58 Correct 435 ms 37248 KB Output is correct
59 Correct 123 ms 9800 KB Output is correct
60 Correct 671 ms 40476 KB Output is correct
61 Correct 671 ms 38372 KB Output is correct
62 Correct 646 ms 42060 KB Output is correct
63 Correct 628 ms 42632 KB Output is correct
64 Correct 2 ms 460 KB Output is correct
65 Correct 2 ms 588 KB Output is correct
66 Correct 2 ms 460 KB Output is correct
67 Correct 2 ms 332 KB Output is correct
68 Correct 1 ms 460 KB Output is correct
69 Correct 3 ms 684 KB Output is correct
70 Correct 3 ms 588 KB Output is correct
71 Correct 3 ms 588 KB Output is correct
72 Correct 2 ms 588 KB Output is correct
73 Correct 3 ms 588 KB Output is correct
74 Correct 284 ms 35280 KB Output is correct
75 Correct 247 ms 37976 KB Output is correct
76 Correct 208 ms 36136 KB Output is correct
77 Correct 203 ms 36492 KB Output is correct
78 Correct 133 ms 14844 KB Output is correct
79 Correct 111 ms 12488 KB Output is correct
80 Correct 220 ms 29456 KB Output is correct
81 Correct 366 ms 44228 KB Output is correct
82 Correct 296 ms 44000 KB Output is correct
83 Correct 430 ms 49292 KB Output is correct
84 Correct 257 ms 43552 KB Output is correct
85 Correct 326 ms 43544 KB Output is correct
86 Correct 112 ms 14320 KB Output is correct
87 Correct 602 ms 41816 KB Output is correct
88 Correct 653 ms 41948 KB Output is correct
89 Correct 374 ms 38236 KB Output is correct
90 Correct 232 ms 18452 KB Output is correct
91 Correct 268 ms 19236 KB Output is correct
92 Correct 389 ms 33404 KB Output is correct
93 Correct 720 ms 48468 KB Output is correct
94 Correct 549 ms 47700 KB Output is correct
95 Correct 873 ms 53088 KB Output is correct
96 Correct 682 ms 44956 KB Output is correct
97 Correct 477 ms 44524 KB Output is correct