oj.uz

Submission #865061

# Submission time Handle Problem Language Result Execution time Memory
865061 2023-10-24T05:00:38 Z jk410 Swapping Cities (APIO20_swap) C++17
100 / 100
 213 ms 66540 KB 
#include "swap.h"
#include <vector>
#include <algorithm>
#include <functional>
#define all(v) v.begin(),v.end()
using namespace std;
struct edge{
    int u,v,cost;
};
struct node{
    int cost;
    bool flag;
};
const int MAX=18;
vector<node> nodes;
vector<vector<int>> child;
vector<int> depth;
vector<vector<int>> par(MAX+1);
vector<int> ans;
void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W){
    vector<edge> edges(M);
    vector<int> group(N+M);
    vector<int> deg(N);
    nodes.resize(N+M);
    child.resize(N+M);
    depth.resize(N+M);
    for (int i=0; i<=MAX; i++)
        par[i].resize(N+M);
    ans.resize(N+M);
    for (int i=0; i<M; i++)
        edges[i]={U[i],V[i],W[i]};
    sort(all(edges),[&](edge a,edge b)->bool{
        return a.cost<b.cost;
    });
    for (int i=0; i<N+M; i++){
        group[i]=i;
        nodes[i]={0,false};
        par[0][i]=i;
    }
    function<int(int)> getGroup=[&](int v)->int{
        if (group[v]==v)
            return v;
        return group[v]=getGroup(group[v]);
    };
    for (int i=0; i<M; i++){
        edge e=edges[i];
        nodes[i+N].cost=e.cost;
        deg[e.u]++;
        deg[e.v]++;
        int u=getGroup(e.u),v=getGroup(e.v);
        if (deg[e.u]>2||deg[e.v]>2||nodes[u].flag||nodes[v].flag)
            nodes[i+N].flag=true;
        if (u==v){
            group[u]=i+N;
            child[i+N].push_back(u);
            par[0][u]=i+N;
            nodes[i+N].flag=true;
            continue;
        }
        group[u]=group[v]=i+N;
        child[i+N].push_back(u);
        child[i+N].push_back(v);
        par[0][u]=par[0][v]=i+N;
    }
    for (int t=1; t<=MAX; t++){
        for (int i=0; i<N+M; i++)
            par[t][i]=par[t-1][par[t-1][i]];
    }
    function<void(int)> dfs=[&](int v){
        for (int i:child[v]){
            depth[i]=depth[v]+1;
            ans[i]=(nodes[i].flag?nodes[i].cost:ans[v]);
            dfs(i);
        }
    };
    for (int i=0; i<N+M; i++){
        if (par[0][i]!=i)
            continue;
        ans[i]=(nodes[i].flag?nodes[i].cost:-1);
        dfs(i);
    }
}
int getLCA(int u,int v){
    if (depth[u]>depth[v])
        swap(u,v);
    for (int i=0,t=depth[v]-depth[u]; t; i++,t>>=1){
        if (t&1)
            v=par[i][v];
    }
    if (u==v)
        return u;
    for (int t=MAX; t>=0; t--){
        if (par[t][u]!=par[t][v]){
            u=par[t][u];
            v=par[t][v];
        }
    }
    return par[0][u];
}
int getMinimumFuelCapacity(int X, int Y){
    return ans[getLCA(X,Y)];
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 644 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 47 ms 24392 KB Output is correct
10 Correct 60 ms 29776 KB Output is correct
11 Correct 58 ms 29196 KB Output is correct
12 Correct 61 ms 30808 KB Output is correct
13 Correct 60 ms 35664 KB Output is correct
14 Correct 56 ms 24404 KB Output is correct
15 Correct 152 ms 31312 KB Output is correct
16 Correct 143 ms 30548 KB Output is correct
17 Correct 154 ms 32584 KB Output is correct
18 Correct 161 ms 37204 KB Output is correct
19 Correct 56 ms 8340 KB Output is correct
20 Correct 135 ms 31688 KB Output is correct
21 Correct 130 ms 30208 KB Output is correct
22 Correct 151 ms 32596 KB Output is correct
23 Correct 181 ms 37204 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 161 ms 39640 KB Output is correct
4 Correct 158 ms 45716 KB Output is correct
5 Correct 164 ms 44328 KB Output is correct
6 Correct 158 ms 45396 KB Output is correct
7 Correct 171 ms 44696 KB Output is correct
8 Correct 150 ms 43092 KB Output is correct
9 Correct 163 ms 44580 KB Output is correct
10 Correct 188 ms 42712 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 644 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 692 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 940 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 728 KB Output is correct
25 Correct 1 ms 860 KB Output is correct
26 Correct 1 ms 860 KB Output is correct
27 Correct 1 ms 604 KB Output is correct
28 Correct 1 ms 856 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 644 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 47 ms 24392 KB Output is correct
11 Correct 60 ms 29776 KB Output is correct
12 Correct 58 ms 29196 KB Output is correct
13 Correct 61 ms 30808 KB Output is correct
14 Correct 60 ms 35664 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 600 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 692 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 1 ms 940 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 1 ms 728 KB Output is correct
30 Correct 1 ms 860 KB Output is correct
31 Correct 1 ms 860 KB Output is correct
32 Correct 1 ms 604 KB Output is correct
33 Correct 1 ms 856 KB Output is correct
34 Correct 11 ms 4696 KB Output is correct
35 Correct 63 ms 32760 KB Output is correct
36 Correct 61 ms 32592 KB Output is correct
37 Correct 70 ms 32864 KB Output is correct
38 Correct 60 ms 32340 KB Output is correct
39 Correct 61 ms 32188 KB Output is correct
40 Correct 55 ms 29524 KB Output is correct
41 Correct 64 ms 33108 KB Output is correct
42 Correct 63 ms 32688 KB Output is correct
43 Correct 55 ms 38832 KB Output is correct
44 Correct 63 ms 33000 KB Output is correct
45 Correct 94 ms 48720 KB Output is correct
46 Correct 63 ms 32688 KB Output is correct
47 Correct 67 ms 32944 KB Output is correct
48 Correct 70 ms 38324 KB Output is correct
49 Correct 82 ms 46944 KB Output is correct
50 Correct 69 ms 36720 KB Output is correct
51 Correct 83 ms 42496 KB Output is correct
52 Correct 107 ms 51540 KB Output is correct
53 Correct 111 ms 54616 KB Output is correct
54 Correct 124 ms 62548 KB Output is correct
55 Correct 54 ms 38224 KB Output is correct
56 Correct 113 ms 57284 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 644 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 47 ms 24392 KB Output is correct
10 Correct 60 ms 29776 KB Output is correct
11 Correct 58 ms 29196 KB Output is correct
12 Correct 61 ms 30808 KB Output is correct
13 Correct 60 ms 35664 KB Output is correct
14 Correct 56 ms 24404 KB Output is correct
15 Correct 152 ms 31312 KB Output is correct
16 Correct 143 ms 30548 KB Output is correct
17 Correct 154 ms 32584 KB Output is correct
18 Correct 161 ms 37204 KB Output is correct
19 Correct 161 ms 39640 KB Output is correct
20 Correct 158 ms 45716 KB Output is correct
21 Correct 164 ms 44328 KB Output is correct
22 Correct 158 ms 45396 KB Output is correct
23 Correct 171 ms 44696 KB Output is correct
24 Correct 150 ms 43092 KB Output is correct
25 Correct 163 ms 44580 KB Output is correct
26 Correct 188 ms 42712 KB Output is correct
27 Correct 1 ms 604 KB Output is correct
28 Correct 1 ms 600 KB Output is correct
29 Correct 1 ms 604 KB Output is correct
30 Correct 1 ms 604 KB Output is correct
31 Correct 1 ms 604 KB Output is correct
32 Correct 1 ms 604 KB Output is correct
33 Correct 1 ms 692 KB Output is correct
34 Correct 1 ms 604 KB Output is correct
35 Correct 1 ms 604 KB Output is correct
36 Correct 11 ms 4696 KB Output is correct
37 Correct 63 ms 32760 KB Output is correct
38 Correct 61 ms 32592 KB Output is correct
39 Correct 70 ms 32864 KB Output is correct
40 Correct 60 ms 32340 KB Output is correct
41 Correct 61 ms 32188 KB Output is correct
42 Correct 55 ms 29524 KB Output is correct
43 Correct 64 ms 33108 KB Output is correct
44 Correct 63 ms 32688 KB Output is correct
45 Correct 55 ms 38832 KB Output is correct
46 Correct 63 ms 33000 KB Output is correct
47 Correct 13 ms 4808 KB Output is correct
48 Correct 130 ms 36672 KB Output is correct
49 Correct 137 ms 36688 KB Output is correct
50 Correct 139 ms 36436 KB Output is correct
51 Correct 136 ms 36324 KB Output is correct
52 Correct 136 ms 34392 KB Output is correct
53 Correct 136 ms 26240 KB Output is correct
54 Correct 142 ms 36944 KB Output is correct
55 Correct 143 ms 36696 KB Output is correct
56 Correct 171 ms 41556 KB Output is correct
57 Correct 150 ms 36944 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 644 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 47 ms 24392 KB Output is correct
11 Correct 60 ms 29776 KB Output is correct
12 Correct 58 ms 29196 KB Output is correct
13 Correct 61 ms 30808 KB Output is correct
14 Correct 60 ms 35664 KB Output is correct
15 Correct 56 ms 24404 KB Output is correct
16 Correct 152 ms 31312 KB Output is correct
17 Correct 143 ms 30548 KB Output is correct
18 Correct 154 ms 32584 KB Output is correct
19 Correct 161 ms 37204 KB Output is correct
20 Correct 161 ms 39640 KB Output is correct
21 Correct 158 ms 45716 KB Output is correct
22 Correct 164 ms 44328 KB Output is correct
23 Correct 158 ms 45396 KB Output is correct
24 Correct 171 ms 44696 KB Output is correct
25 Correct 150 ms 43092 KB Output is correct
26 Correct 163 ms 44580 KB Output is correct
27 Correct 188 ms 42712 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 1 ms 600 KB Output is correct
30 Correct 1 ms 604 KB Output is correct
31 Correct 1 ms 604 KB Output is correct
32 Correct 1 ms 604 KB Output is correct
33 Correct 1 ms 604 KB Output is correct
34 Correct 1 ms 692 KB Output is correct
35 Correct 1 ms 604 KB Output is correct
36 Correct 1 ms 604 KB Output is correct
37 Correct 11 ms 4696 KB Output is correct
38 Correct 63 ms 32760 KB Output is correct
39 Correct 61 ms 32592 KB Output is correct
40 Correct 70 ms 32864 KB Output is correct
41 Correct 60 ms 32340 KB Output is correct
42 Correct 61 ms 32188 KB Output is correct
43 Correct 55 ms 29524 KB Output is correct
44 Correct 64 ms 33108 KB Output is correct
45 Correct 63 ms 32688 KB Output is correct
46 Correct 55 ms 38832 KB Output is correct
47 Correct 63 ms 33000 KB Output is correct
48 Correct 13 ms 4808 KB Output is correct
49 Correct 130 ms 36672 KB Output is correct
50 Correct 137 ms 36688 KB Output is correct
51 Correct 139 ms 36436 KB Output is correct
52 Correct 136 ms 36324 KB Output is correct
53 Correct 136 ms 34392 KB Output is correct
54 Correct 136 ms 26240 KB Output is correct
55 Correct 142 ms 36944 KB Output is correct
56 Correct 143 ms 36696 KB Output is correct
57 Correct 171 ms 41556 KB Output is correct
58 Correct 150 ms 36944 KB Output is correct
59 Correct 56 ms 8340 KB Output is correct
60 Correct 135 ms 31688 KB Output is correct
61 Correct 130 ms 30208 KB Output is correct
62 Correct 151 ms 32596 KB Output is correct
63 Correct 181 ms 37204 KB Output is correct
64 Correct 1 ms 604 KB Output is correct
65 Correct 1 ms 604 KB Output is correct
66 Correct 1 ms 604 KB Output is correct
67 Correct 1 ms 940 KB Output is correct
68 Correct 1 ms 604 KB Output is correct
69 Correct 1 ms 728 KB Output is correct
70 Correct 1 ms 860 KB Output is correct
71 Correct 1 ms 860 KB Output is correct
72 Correct 1 ms 604 KB Output is correct
73 Correct 1 ms 856 KB Output is correct
74 Correct 94 ms 48720 KB Output is correct
75 Correct 63 ms 32688 KB Output is correct
76 Correct 67 ms 32944 KB Output is correct
77 Correct 70 ms 38324 KB Output is correct
78 Correct 82 ms 46944 KB Output is correct
79 Correct 69 ms 36720 KB Output is correct
80 Correct 83 ms 42496 KB Output is correct
81 Correct 107 ms 51540 KB Output is correct
82 Correct 111 ms 54616 KB Output is correct
83 Correct 124 ms 62548 KB Output is correct
84 Correct 54 ms 38224 KB Output is correct
85 Correct 113 ms 57284 KB Output is correct
86 Correct 72 ms 17928 KB Output is correct
87 Correct 133 ms 36476 KB Output is correct
88 Correct 133 ms 36664 KB Output is correct
89 Correct 168 ms 40700 KB Output is correct
90 Correct 153 ms 53076 KB Output is correct
91 Correct 157 ms 48724 KB Output is correct
92 Correct 174 ms 44268 KB Output is correct
93 Correct 189 ms 54372 KB Output is correct
94 Correct 213 ms 58364 KB Output is correct
95 Correct 201 ms 66540 KB Output is correct
96 Correct 157 ms 42060 KB Output is correct
97 Correct 196 ms 50252 KB Output is correct