#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
struct edge
{
int v, u, w;
edge(int _v, int _u, int _w)
{
v = _v;
u = _u;
w = _w;
}
};
const int maxn = 4e5 + 10;
const int inf = 1e9 + 10;
int n, m, lead[maxn], rnk[maxn], is_fixed[maxn];
int find_leader(int v)
{
if (v == lead[v])
return v;
return (lead[v] = find_leader(lead[v]));
}
vector < int > g[maxn];
int vertex_cnt, cost[maxn], deg[maxn];
void unite(int v, int u, int w)
{
deg[v] ++;
deg[u] ++;
bool deg_v = (deg[v] > 2), deg_u = (deg[u] > 2);
v = find_leader(v);
u = find_leader(u);
int cur = ++ vertex_cnt;
lead[cur] = cur;
cost[cur] = w;
if (v == u)
{
lead[v] = cur;
is_fixed[cur] = 1;
g[cur].push_back(v);
//cout << cur << " " << v << endl;
return;
}
is_fixed[cur] = max(is_fixed[v], is_fixed[u]);
if (deg_v || deg_u)
is_fixed[cur] = 1;
lead[v] = lead[u] = cur;
g[cur].push_back(v);
g[cur].push_back(u);
//cout << cur << " " << v << endl;
//cout << cur << " " << u << endl;
}
bool cmp(edge e1, edge e2)
{
return e1.w < e2.w;
}
vector < edge > edges;
const int maxlog = 22;
int par[maxn], jump[maxn], timer, lvl[maxn];
int tin[maxn], fs[2 * maxn], lg[2 * maxn], dp[maxlog][2 * maxn];
void dfs(int v)
{
///cout << v << " : " << is_fixed[v] << endl;
if (is_fixed[v])
jump[v] = v;
else
jump[v] = jump[par[v]];
fs[++ timer] = v;
tin[v] = timer;
for (int u : g[v])
{
lvl[u] = lvl[v] + 1;
par[u] = v;
dfs(u);
fs[++ timer] = v;
}
}
void build_sparse_table()
{
for (int i = 1; i <= timer; i ++)
{
lg[i] = lg[i / 2] + 1;
dp[0][i] = fs[i];
}
for (int j = 1; j < lg[timer]; j ++)
for (int i = 1; i <= (timer - (1 << j) + 1); i ++)
{
dp[j][i] = dp[j - 1][i + (1 << (j - 1))];
if (lvl[dp[j - 1][i]] < lvl[dp[j][i]])
dp[j][i] = dp[j - 1][i];
}
}
int query_lca(int v, int u)
{
int l = tin[v], r = tin[u];
if (l > r)
swap(l, r);
int len = lg[r - l + 1] - 1, ans = dp[len][r - (1 << len) + 1];
if (lvl[dp[len][l]] < lvl[ans])
ans = dp[len][l];
return ans;
}
void init(int N, int M,
vector<int> U, vector<int> V, vector<int> W)
{
n = N;
m = M;
for (int i = 0; i < m; i ++)
{
edges.push_back(edge(U[i], V[i], W[i]));
}
for (int i = 0; i < n; i ++)
lead[i] = i;
vertex_cnt = n - 1;
sort(edges.begin(), edges.end(), cmp);
for (int i = 0; i < edges.size(); i ++)
{
unite(edges[i].v, edges[i].u, edges[i].w);
}
lvl[vertex_cnt] = 1;
jump[vertex_cnt + 1] = vertex_cnt + 1;
par[vertex_cnt] = vertex_cnt + 1;
dfs(vertex_cnt);
build_sparse_table();
}
int getMinimumFuelCapacity(int X, int Y)
{
int lca = query_lca(X, Y);
lca = jump[lca];
if (lca == vertex_cnt + 1)
return -1;
///cout << "lca " << lca << endl;
return cost[lca];
}
Compilation message
swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:134:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | for (int i = 0; i < edges.size(); i ++)
| ~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9760 KB |
Output is correct |
3 |
Correct |
5 ms |
9712 KB |
Output is correct |
4 |
Correct |
5 ms |
9940 KB |
Output is correct |
5 |
Correct |
6 ms |
10068 KB |
Output is correct |
6 |
Correct |
6 ms |
10096 KB |
Output is correct |
7 |
Correct |
6 ms |
10068 KB |
Output is correct |
8 |
Correct |
8 ms |
10220 KB |
Output is correct |
9 |
Correct |
87 ms |
42756 KB |
Output is correct |
10 |
Correct |
99 ms |
50592 KB |
Output is correct |
11 |
Correct |
100 ms |
49900 KB |
Output is correct |
12 |
Correct |
122 ms |
52460 KB |
Output is correct |
13 |
Correct |
107 ms |
56260 KB |
Output is correct |
14 |
Correct |
97 ms |
42840 KB |
Output is correct |
15 |
Correct |
170 ms |
52720 KB |
Output is correct |
16 |
Correct |
179 ms |
51584 KB |
Output is correct |
17 |
Correct |
170 ms |
54244 KB |
Output is correct |
18 |
Correct |
149 ms |
58040 KB |
Output is correct |
19 |
Correct |
66 ms |
19396 KB |
Output is correct |
20 |
Correct |
173 ms |
58316 KB |
Output is correct |
21 |
Correct |
158 ms |
56852 KB |
Output is correct |
22 |
Correct |
187 ms |
59968 KB |
Output is correct |
23 |
Correct |
151 ms |
63936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9760 KB |
Output is correct |
3 |
Correct |
131 ms |
60496 KB |
Output is correct |
4 |
Correct |
167 ms |
66868 KB |
Output is correct |
5 |
Correct |
144 ms |
65356 KB |
Output is correct |
6 |
Correct |
155 ms |
66528 KB |
Output is correct |
7 |
Correct |
145 ms |
66128 KB |
Output is correct |
8 |
Correct |
139 ms |
63856 KB |
Output is correct |
9 |
Correct |
157 ms |
65696 KB |
Output is correct |
10 |
Correct |
140 ms |
63356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9760 KB |
Output is correct |
3 |
Correct |
5 ms |
9712 KB |
Output is correct |
4 |
Correct |
5 ms |
9940 KB |
Output is correct |
5 |
Correct |
6 ms |
10068 KB |
Output is correct |
6 |
Correct |
6 ms |
10096 KB |
Output is correct |
7 |
Correct |
6 ms |
10068 KB |
Output is correct |
8 |
Correct |
8 ms |
10220 KB |
Output is correct |
9 |
Correct |
6 ms |
9684 KB |
Output is correct |
10 |
Correct |
5 ms |
10068 KB |
Output is correct |
11 |
Correct |
6 ms |
10068 KB |
Output is correct |
12 |
Correct |
5 ms |
10120 KB |
Output is correct |
13 |
Correct |
6 ms |
10068 KB |
Output is correct |
14 |
Correct |
5 ms |
10068 KB |
Output is correct |
15 |
Correct |
6 ms |
10068 KB |
Output is correct |
16 |
Correct |
6 ms |
10068 KB |
Output is correct |
17 |
Correct |
5 ms |
10196 KB |
Output is correct |
18 |
Correct |
7 ms |
10196 KB |
Output is correct |
19 |
Correct |
6 ms |
10068 KB |
Output is correct |
20 |
Correct |
6 ms |
10068 KB |
Output is correct |
21 |
Correct |
6 ms |
10196 KB |
Output is correct |
22 |
Correct |
9 ms |
10324 KB |
Output is correct |
23 |
Correct |
9 ms |
10068 KB |
Output is correct |
24 |
Correct |
8 ms |
10384 KB |
Output is correct |
25 |
Correct |
7 ms |
10324 KB |
Output is correct |
26 |
Correct |
6 ms |
10452 KB |
Output is correct |
27 |
Correct |
5 ms |
10196 KB |
Output is correct |
28 |
Correct |
7 ms |
10452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9760 KB |
Output is correct |
4 |
Correct |
5 ms |
9712 KB |
Output is correct |
5 |
Correct |
5 ms |
9940 KB |
Output is correct |
6 |
Correct |
6 ms |
10068 KB |
Output is correct |
7 |
Correct |
6 ms |
10096 KB |
Output is correct |
8 |
Correct |
6 ms |
10068 KB |
Output is correct |
9 |
Correct |
8 ms |
10220 KB |
Output is correct |
10 |
Correct |
87 ms |
42756 KB |
Output is correct |
11 |
Correct |
99 ms |
50592 KB |
Output is correct |
12 |
Correct |
100 ms |
49900 KB |
Output is correct |
13 |
Correct |
122 ms |
52460 KB |
Output is correct |
14 |
Correct |
107 ms |
56260 KB |
Output is correct |
15 |
Correct |
5 ms |
10068 KB |
Output is correct |
16 |
Correct |
6 ms |
10068 KB |
Output is correct |
17 |
Correct |
5 ms |
10120 KB |
Output is correct |
18 |
Correct |
6 ms |
10068 KB |
Output is correct |
19 |
Correct |
5 ms |
10068 KB |
Output is correct |
20 |
Correct |
6 ms |
10068 KB |
Output is correct |
21 |
Correct |
6 ms |
10068 KB |
Output is correct |
22 |
Correct |
5 ms |
10196 KB |
Output is correct |
23 |
Correct |
7 ms |
10196 KB |
Output is correct |
24 |
Correct |
6 ms |
10068 KB |
Output is correct |
25 |
Correct |
6 ms |
10068 KB |
Output is correct |
26 |
Correct |
6 ms |
10196 KB |
Output is correct |
27 |
Correct |
9 ms |
10324 KB |
Output is correct |
28 |
Correct |
9 ms |
10068 KB |
Output is correct |
29 |
Correct |
8 ms |
10384 KB |
Output is correct |
30 |
Correct |
7 ms |
10324 KB |
Output is correct |
31 |
Correct |
6 ms |
10452 KB |
Output is correct |
32 |
Correct |
5 ms |
10196 KB |
Output is correct |
33 |
Correct |
7 ms |
10452 KB |
Output is correct |
34 |
Correct |
17 ms |
15044 KB |
Output is correct |
35 |
Correct |
108 ms |
52344 KB |
Output is correct |
36 |
Correct |
109 ms |
52420 KB |
Output is correct |
37 |
Correct |
115 ms |
52288 KB |
Output is correct |
38 |
Correct |
109 ms |
51732 KB |
Output is correct |
39 |
Correct |
112 ms |
51588 KB |
Output is correct |
40 |
Correct |
101 ms |
47936 KB |
Output is correct |
41 |
Correct |
131 ms |
52432 KB |
Output is correct |
42 |
Correct |
105 ms |
52356 KB |
Output is correct |
43 |
Correct |
83 ms |
57712 KB |
Output is correct |
44 |
Correct |
112 ms |
52420 KB |
Output is correct |
45 |
Correct |
139 ms |
67748 KB |
Output is correct |
46 |
Correct |
125 ms |
52340 KB |
Output is correct |
47 |
Correct |
102 ms |
52500 KB |
Output is correct |
48 |
Correct |
115 ms |
57812 KB |
Output is correct |
49 |
Correct |
112 ms |
60984 KB |
Output is correct |
50 |
Correct |
89 ms |
49388 KB |
Output is correct |
51 |
Correct |
111 ms |
59632 KB |
Output is correct |
52 |
Correct |
152 ms |
73128 KB |
Output is correct |
53 |
Correct |
193 ms |
77348 KB |
Output is correct |
54 |
Correct |
198 ms |
86340 KB |
Output is correct |
55 |
Correct |
85 ms |
58864 KB |
Output is correct |
56 |
Correct |
196 ms |
82600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9760 KB |
Output is correct |
3 |
Correct |
5 ms |
9712 KB |
Output is correct |
4 |
Correct |
5 ms |
9940 KB |
Output is correct |
5 |
Correct |
6 ms |
10068 KB |
Output is correct |
6 |
Correct |
6 ms |
10096 KB |
Output is correct |
7 |
Correct |
6 ms |
10068 KB |
Output is correct |
8 |
Correct |
8 ms |
10220 KB |
Output is correct |
9 |
Correct |
87 ms |
42756 KB |
Output is correct |
10 |
Correct |
99 ms |
50592 KB |
Output is correct |
11 |
Correct |
100 ms |
49900 KB |
Output is correct |
12 |
Correct |
122 ms |
52460 KB |
Output is correct |
13 |
Correct |
107 ms |
56260 KB |
Output is correct |
14 |
Correct |
97 ms |
42840 KB |
Output is correct |
15 |
Correct |
170 ms |
52720 KB |
Output is correct |
16 |
Correct |
179 ms |
51584 KB |
Output is correct |
17 |
Correct |
170 ms |
54244 KB |
Output is correct |
18 |
Correct |
149 ms |
58040 KB |
Output is correct |
19 |
Correct |
131 ms |
60496 KB |
Output is correct |
20 |
Correct |
167 ms |
66868 KB |
Output is correct |
21 |
Correct |
144 ms |
65356 KB |
Output is correct |
22 |
Correct |
155 ms |
66528 KB |
Output is correct |
23 |
Correct |
145 ms |
66128 KB |
Output is correct |
24 |
Correct |
139 ms |
63856 KB |
Output is correct |
25 |
Correct |
157 ms |
65696 KB |
Output is correct |
26 |
Correct |
140 ms |
63356 KB |
Output is correct |
27 |
Correct |
5 ms |
10068 KB |
Output is correct |
28 |
Correct |
6 ms |
10068 KB |
Output is correct |
29 |
Correct |
5 ms |
10120 KB |
Output is correct |
30 |
Correct |
6 ms |
10068 KB |
Output is correct |
31 |
Correct |
5 ms |
10068 KB |
Output is correct |
32 |
Correct |
6 ms |
10068 KB |
Output is correct |
33 |
Correct |
6 ms |
10068 KB |
Output is correct |
34 |
Correct |
5 ms |
10196 KB |
Output is correct |
35 |
Correct |
7 ms |
10196 KB |
Output is correct |
36 |
Correct |
17 ms |
15044 KB |
Output is correct |
37 |
Correct |
108 ms |
52344 KB |
Output is correct |
38 |
Correct |
109 ms |
52420 KB |
Output is correct |
39 |
Correct |
115 ms |
52288 KB |
Output is correct |
40 |
Correct |
109 ms |
51732 KB |
Output is correct |
41 |
Correct |
112 ms |
51588 KB |
Output is correct |
42 |
Correct |
101 ms |
47936 KB |
Output is correct |
43 |
Correct |
131 ms |
52432 KB |
Output is correct |
44 |
Correct |
105 ms |
52356 KB |
Output is correct |
45 |
Correct |
83 ms |
57712 KB |
Output is correct |
46 |
Correct |
112 ms |
52420 KB |
Output is correct |
47 |
Correct |
23 ms |
15324 KB |
Output is correct |
48 |
Correct |
176 ms |
59136 KB |
Output is correct |
49 |
Correct |
189 ms |
59124 KB |
Output is correct |
50 |
Correct |
173 ms |
58960 KB |
Output is correct |
51 |
Correct |
181 ms |
58788 KB |
Output is correct |
52 |
Correct |
163 ms |
56128 KB |
Output is correct |
53 |
Correct |
139 ms |
44776 KB |
Output is correct |
54 |
Correct |
185 ms |
59952 KB |
Output is correct |
55 |
Correct |
172 ms |
59212 KB |
Output is correct |
56 |
Correct |
157 ms |
63180 KB |
Output is correct |
57 |
Correct |
174 ms |
60124 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9760 KB |
Output is correct |
4 |
Correct |
5 ms |
9712 KB |
Output is correct |
5 |
Correct |
5 ms |
9940 KB |
Output is correct |
6 |
Correct |
6 ms |
10068 KB |
Output is correct |
7 |
Correct |
6 ms |
10096 KB |
Output is correct |
8 |
Correct |
6 ms |
10068 KB |
Output is correct |
9 |
Correct |
8 ms |
10220 KB |
Output is correct |
10 |
Correct |
87 ms |
42756 KB |
Output is correct |
11 |
Correct |
99 ms |
50592 KB |
Output is correct |
12 |
Correct |
100 ms |
49900 KB |
Output is correct |
13 |
Correct |
122 ms |
52460 KB |
Output is correct |
14 |
Correct |
107 ms |
56260 KB |
Output is correct |
15 |
Correct |
97 ms |
42840 KB |
Output is correct |
16 |
Correct |
170 ms |
52720 KB |
Output is correct |
17 |
Correct |
179 ms |
51584 KB |
Output is correct |
18 |
Correct |
170 ms |
54244 KB |
Output is correct |
19 |
Correct |
149 ms |
58040 KB |
Output is correct |
20 |
Correct |
131 ms |
60496 KB |
Output is correct |
21 |
Correct |
167 ms |
66868 KB |
Output is correct |
22 |
Correct |
144 ms |
65356 KB |
Output is correct |
23 |
Correct |
155 ms |
66528 KB |
Output is correct |
24 |
Correct |
145 ms |
66128 KB |
Output is correct |
25 |
Correct |
139 ms |
63856 KB |
Output is correct |
26 |
Correct |
157 ms |
65696 KB |
Output is correct |
27 |
Correct |
140 ms |
63356 KB |
Output is correct |
28 |
Correct |
5 ms |
10068 KB |
Output is correct |
29 |
Correct |
6 ms |
10068 KB |
Output is correct |
30 |
Correct |
5 ms |
10120 KB |
Output is correct |
31 |
Correct |
6 ms |
10068 KB |
Output is correct |
32 |
Correct |
5 ms |
10068 KB |
Output is correct |
33 |
Correct |
6 ms |
10068 KB |
Output is correct |
34 |
Correct |
6 ms |
10068 KB |
Output is correct |
35 |
Correct |
5 ms |
10196 KB |
Output is correct |
36 |
Correct |
7 ms |
10196 KB |
Output is correct |
37 |
Correct |
17 ms |
15044 KB |
Output is correct |
38 |
Correct |
108 ms |
52344 KB |
Output is correct |
39 |
Correct |
109 ms |
52420 KB |
Output is correct |
40 |
Correct |
115 ms |
52288 KB |
Output is correct |
41 |
Correct |
109 ms |
51732 KB |
Output is correct |
42 |
Correct |
112 ms |
51588 KB |
Output is correct |
43 |
Correct |
101 ms |
47936 KB |
Output is correct |
44 |
Correct |
131 ms |
52432 KB |
Output is correct |
45 |
Correct |
105 ms |
52356 KB |
Output is correct |
46 |
Correct |
83 ms |
57712 KB |
Output is correct |
47 |
Correct |
112 ms |
52420 KB |
Output is correct |
48 |
Correct |
23 ms |
15324 KB |
Output is correct |
49 |
Correct |
176 ms |
59136 KB |
Output is correct |
50 |
Correct |
189 ms |
59124 KB |
Output is correct |
51 |
Correct |
173 ms |
58960 KB |
Output is correct |
52 |
Correct |
181 ms |
58788 KB |
Output is correct |
53 |
Correct |
163 ms |
56128 KB |
Output is correct |
54 |
Correct |
139 ms |
44776 KB |
Output is correct |
55 |
Correct |
185 ms |
59952 KB |
Output is correct |
56 |
Correct |
172 ms |
59212 KB |
Output is correct |
57 |
Correct |
157 ms |
63180 KB |
Output is correct |
58 |
Correct |
174 ms |
60124 KB |
Output is correct |
59 |
Correct |
66 ms |
19396 KB |
Output is correct |
60 |
Correct |
173 ms |
58316 KB |
Output is correct |
61 |
Correct |
158 ms |
56852 KB |
Output is correct |
62 |
Correct |
187 ms |
59968 KB |
Output is correct |
63 |
Correct |
151 ms |
63936 KB |
Output is correct |
64 |
Correct |
6 ms |
10068 KB |
Output is correct |
65 |
Correct |
6 ms |
10068 KB |
Output is correct |
66 |
Correct |
6 ms |
10196 KB |
Output is correct |
67 |
Correct |
9 ms |
10324 KB |
Output is correct |
68 |
Correct |
9 ms |
10068 KB |
Output is correct |
69 |
Correct |
8 ms |
10384 KB |
Output is correct |
70 |
Correct |
7 ms |
10324 KB |
Output is correct |
71 |
Correct |
6 ms |
10452 KB |
Output is correct |
72 |
Correct |
5 ms |
10196 KB |
Output is correct |
73 |
Correct |
7 ms |
10452 KB |
Output is correct |
74 |
Correct |
139 ms |
67748 KB |
Output is correct |
75 |
Correct |
125 ms |
52340 KB |
Output is correct |
76 |
Correct |
102 ms |
52500 KB |
Output is correct |
77 |
Correct |
115 ms |
57812 KB |
Output is correct |
78 |
Correct |
112 ms |
60984 KB |
Output is correct |
79 |
Correct |
89 ms |
49388 KB |
Output is correct |
80 |
Correct |
111 ms |
59632 KB |
Output is correct |
81 |
Correct |
152 ms |
73128 KB |
Output is correct |
82 |
Correct |
193 ms |
77348 KB |
Output is correct |
83 |
Correct |
198 ms |
86340 KB |
Output is correct |
84 |
Correct |
85 ms |
58864 KB |
Output is correct |
85 |
Correct |
196 ms |
82600 KB |
Output is correct |
86 |
Correct |
62 ms |
31320 KB |
Output is correct |
87 |
Correct |
181 ms |
59184 KB |
Output is correct |
88 |
Correct |
161 ms |
59096 KB |
Output is correct |
89 |
Correct |
182 ms |
62316 KB |
Output is correct |
90 |
Correct |
167 ms |
70996 KB |
Output is correct |
91 |
Correct |
180 ms |
66676 KB |
Output is correct |
92 |
Correct |
184 ms |
65264 KB |
Output is correct |
93 |
Correct |
234 ms |
80168 KB |
Output is correct |
94 |
Correct |
254 ms |
85444 KB |
Output is correct |
95 |
Correct |
262 ms |
94264 KB |
Output is correct |
96 |
Correct |
160 ms |
63564 KB |
Output is correct |
97 |
Correct |
254 ms |
74332 KB |
Output is correct |