#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long un;
typedef vector<un> vuc;
typedef vector<bool> vol;
#define vec vector
#define REP(i, a, b) for (un i = (un)a; i < (un)b; i++)
#define FEAC(i, a) for (auto&& i : a)
constexpr un INF = 1e10;
constexpr un L = 20;
vuc otec;
vuc delka;
vuc chlup;
vuc hloubka;
vec<vuc> s_otec;
vec<vuc> s_delka;
vec<vuc> s_chlup;
vec<vuc> s_pred;
vec<vuc> synove;
vec<vuc> synmin;
vec<vuc> synkde;
un get_min_son(un i, un A = -1, un B = -1){
vuc mins = synmin[i];
vuc kdes = synkde[i];
if (((kdes[0] == A) and (kdes[1] == B)) or ((kdes[0] == B) and (kdes[1] == A))){
return mins[2];
}
if ((kdes[0] == A) or (kdes[0] == B)){
return mins[1];
}
return mins[0];
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
vec<vec<pair<un, un>>> graph(N);
REP(i, 0, M){
graph[U[i]].push_back({V[i], W[i]});
graph[V[i]].push_back({U[i], W[i]});
}
otec = vuc(N, -1);
delka = vuc(N, INF);
chlup = vuc(N, INF);
priority_queue<tuple<un, un, un>> zasob;
zasob.push({-INF, 0, -1});
vol visited(N, false);
while (not zasob.empty())
{
un now, w, dad;
tie(w, now, dad) = zasob.top(); zasob.pop();
if (visited[now]) continue;
visited[now] = true;
otec[now] = dad;
delka[now] = -w;
FEAC(psw, graph[now]){
un son, weight;
tie(son, weight) = psw;
zasob.push({-weight, son, now});
}
}
synove = vec<vuc>(N);
synmin = vec<vuc>(N, vuc(3, INF));
synkde = vec<vuc>(N, vuc(3, -1));
REP(i, 0, N){
FEAC(psw, graph[i]){
un son, weight;
tie(son, weight) = psw;
if (son == otec[i]) continue;
if (otec[son] == i) {
synove[i].push_back(son);
if (weight < synmin[i][0]){
swap(synmin[i][1], synmin[i][2]);
swap(synmin[i][0], synmin[i][1]);
swap(synkde[i][1], synkde[i][2]);
swap(synkde[i][0], synkde[i][1]);
synmin[i][0] = weight;
synkde[i][0] = son;
}
else if (weight < synmin[i][1]){
swap(synmin[i][1], synmin[i][2]);
swap(synkde[i][1], synkde[i][2]);
synmin[i][1] = weight;
synkde[i][1] = son;
}
else if (weight < synmin[i][2]){
synmin[i][2] = weight;
synkde[i][2] = son;
}
}
else{
chlup[i] = min(chlup[i], weight);
}
}
}
s_otec = vec<vuc>(L, vuc(N));
s_delka = vec<vuc>(L, vuc(N));
s_chlup = vec<vuc>(L, vuc(N));
s_pred = vec<vuc>(L, vuc(N));
s_otec[0] = otec;
s_otec[0][0] = 0;
s_delka[0] = delka;
s_delka[0][0] = 0;
s_chlup[0] = vuc(N, INF);
iota(s_pred[0].begin(), s_pred[0].end(), 0);
REP(l, 1, L){
REP(i, 0, N){
s_otec[l][i] = s_otec[l-1][s_otec[l-1][i]];
s_delka[l][i] = max(s_delka[l-1][i], s_delka[l-1][s_otec[l-1][i]]);
s_pred[l][i] = s_pred[l-1][s_otec[l-1][i]];
s_chlup[l][i] = min({s_chlup[l-1][i], s_chlup[l-1][s_otec[l-1][i]],
get_min_son(s_otec[l-1][i], s_pred[l-1][i])});
}
}
hloubka = vuc(N, 0);
stack<pair<un, un>> zas;
zas.push({0, 0});
while (not zas.empty()){
un now, depth;
tie(now, depth) = zas.top(); zas.pop();
hloubka[now] = depth;
FEAC(s, synove[now]){
zas.push({s, depth+1});
}
}
}
int getMinimumFuelCapacity(int X, int Y) {
un chlup_ret = INF;
un main_ret = 0;
if (hloubka[X] > hloubka[Y]) swap(X, Y);
if (hloubka[X] == 0){
while (hloubka[Y] != 1)
{
un t = 0;
while(hloubka[s_otec[t+1][Y]] >= 1) t++;
main_ret = max(main_ret, s_delka[t][Y]);
chlup_ret = min({chlup_ret, get_min_son(s_otec[t][Y], s_pred[t][Y]), s_chlup[t][Y]});
Y = s_otec[t][Y];
}
main_ret = max(delka[Y], main_ret);
return max(main_ret, chlup_ret);
}
while (hloubka[X] != hloubka[Y])
{
un t = 0;
while(hloubka[s_otec[t+1][Y]] >= hloubka[X]) t++;
main_ret = max(main_ret, s_delka[t][Y]);
chlup_ret = min(chlup_ret, s_chlup[t][Y]);
if (X != s_otec[t][Y]) chlup_ret = min({chlup_ret, get_min_son(s_otec[t][Y], s_pred[t][Y])});
Y = s_otec[t][Y];
}
if (X == Y){
return max(chlup_ret, main_ret);
}
while(otec[X] != otec[Y]){
un t;
while(s_otec[t+1][X] != s_otec[t+1][X]) t++;
main_ret = max(main_ret, s_delka[t][Y]);
chlup_ret = min({chlup_ret, get_min_son(s_otec[t][Y], s_pred[t][Y]), s_chlup[t][Y]});
main_ret = max(main_ret, s_delka[t][X]);
chlup_ret = min({chlup_ret, get_min_son(s_otec[t][X], s_pred[t][X]), s_chlup[t][X]});
Y = s_otec[t][Y];
X = s_otec[t][X];
}
main_ret = max({main_ret, delka[X], delka[Y]});
chlup_ret = min({chlup_ret, get_min_son(otec[X], X, Y), delka[otec[X]]});
return max(main_ret, chlup_ret);
}
Compilation message
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:231:39: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
231 | main_ret = max(main_ret, s_delka[t][Y]);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
