#include "swap.h"
#include <iostream>
#include <vector>
#include <algorithm>
#define f first
#define s second
using namespace std;
const int NMAX = 1e5, MMAX = 2e5, inf = 2e9;
int n, m, tata[NMAX+10], rang[NMAX+10], mini[3][NMAX+10], costTata[NMAX+10], dp[20][NMAX+10], dp1[20][NMAX+10], dp2[20][NMAX+10], nivel[NMAX+10];
vector <pair <int, int> > nod[NMAX+10], tree[NMAX+10];
struct Kruskal{
int n1, n2, cost;
}K[MMAX+10];
inline bool cmp(Kruskal a, Kruskal b){
return a.cost < b.cost;
}
int findDaddy(int x){
int r = x, y = x;
while(r != tata[r])
r = tata[r];
while(x != tata[x]){
y = tata[x];
tata[x] = r;
x = y;
}
return r;
}
void unite(int x, int y){
if(rang[x] < rang[y])
tata[x] = y;
else
tata[y] = x;
if(rang[x] == rang[y])
rang[x]++;
}
void dfs(int x, int p = 0){
dp[0][x] = p;
nivel[x] = nivel[p] + 1;
for(auto u : nod[x])
if(u.f != p){
for(int t=0; t<3; t++)
if(mini[t][x] > u.s){
for(int t1=2; t1>t; t1--)
mini[t1][x] = mini[t1-1][x];
mini[t][x] = u.s;
break;
}
}
for(auto u : tree[x])
if(u.f != p){
dfs(u.f, x);
costTata[u.f] = u.s;
}
}
void buildStramosi(){
for(int i=1; i<=n; i++){
if(costTata[i] != mini[0][dp[0][i]])
dp2[0][i] = mini[0][dp[0][i]];
else
dp2[0][i] = mini[1][dp[0][i]];
dp1[0][i] = costTata[i];
}
for(int bit=1; (1<<bit)<=n; bit++)
for(int i=1; i<=n; i++){
dp[bit][i] = dp[bit-1][dp[bit-1][i]];
dp1[bit][i] = max(dp1[bit-1][i], dp1[bit-1][dp[bit-1][i]]);
dp2[bit][i] = min(dp2[bit-1][i], dp2[bit-1][dp[bit-1][i]]);
}
}
pair <int, int> lca(int x, int y){
if(nivel[x] < nivel[y])
swap(x, y);
int dif = nivel[x] - nivel[y], ans = 0;
for(int bit=0; (1<<bit)<=dif; bit++)
if(dif & (1 << bit)){
ans = max(ans, dp1[bit][x]);
x = dp[bit][x];
}
if(x == y)
return {x, ans};
for(int bit=19; bit>=0; bit--)
if(dp[bit][x] != dp[bit][y]){
ans = max(ans, max(dp1[bit][x], dp1[bit][y]));
x = dp[bit][x];
y = dp[bit][y];
}
return {dp[0][x], max(ans, max(dp1[0][x], dp1[0][y]))};
}
int findStr(int x, int k){
for(int bit=0; (1<<bit)<=k; bit++)
if(k & (1 << bit))
x = dp[bit][x];
return x;
}
int minLant(int x, int k){
int ans = inf;
for(int bit=0; (1<<bit)<=k; bit++)
if(k & (1 << bit)){
ans = min(ans, dp1[bit][x]);
x = dp[bit][x];
}
return ans;
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W){
n = N;
m = M;
for(int i=1; i<=n; i++)
tata[i] = i, rang[i] = 1;
for(int i=0; i<m; i++){
int nod1 = U[i] + 1, nod2 = V[i] + 1, cost = W[i];
nod[nod1].push_back({nod2, cost});
nod[nod2].push_back({nod1, cost});
K[i+1] = {nod1, nod2, cost};
}
sort(K+1, K+m+1, cmp);
for(int i=1; i<=m; i++){
int val1 = findDaddy(K[i].n1), val2 = findDaddy(K[i].n2);
if(val1 != val2){
unite(val1, val2);
tree[K[i].n1].push_back({K[i].n2, K[i].cost});
tree[K[i].n2].push_back({K[i].n1, K[i].cost});
}
}
for(int i=1; i<=n; i++)
mini[0][i] = mini[1][i] = mini[2][i] = inf;
costTata[1] = 0;
dfs(1);
buildStramosi();
}
int getMinimumFuelCapacity(int X, int Y){
int x = X + 1, y = Y + 1;
pair <int, int> LCA = lca(x, y);
int val1 = LCA.s, val2 = inf;
if(findStr(y, nivel[y] - nivel[LCA.f]) == x)
swap(x, y);
if(findStr(x, nivel[x] - nivel[LCA.f]) == y){
val2 = mini[1][x];
int val = nivel[x] - nivel[LCA.f] - 1, costVal = costTata[findStr(x, val)];
val2 = min(val2, minLant(x, val));
int c = 0, valx = 0;
bool ok = false;
for(int t=0; t<3 && c<2; t++){
if(!ok && costVal == mini[t][y])
ok = true;
else
c++, valx = max(valx, mini[t][y]);
}
val2 = min(val2, valx);
}
else{
val2 = min(mini[1][x], mini[1][y]);
int val = nivel[x] - nivel[LCA.f] - 1, costVal1 = costTata[findStr(x, val)];
val2 = min(val2, minLant(x, val));
val = nivel[y] - nivel[LCA.f] - 1;
val2 = min(val2, minLant(y, val));
int costVal2 = costTata[findStr(y, val)];
bool ok1 = false, ok2 = false;
for(int t=0; t<3; t++){
if(!ok1 && costVal1 == mini[t][LCA.f])
ok1 = true;
else if(!ok2 && costVal2 == mini[t][LCA.f])
ok2 = true;
else{
val2 = min(val2, mini[t][LCA.f]);
break;
}
}
}
if(val2 == inf)
return -1;
return max(val1, val2);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5076 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
5012 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5076 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 3 |
Correct |
173 ms |
44268 KB |
Output is correct |
| 4 |
Correct |
185 ms |
45724 KB |
Output is correct |
| 5 |
Correct |
185 ms |
45188 KB |
Output is correct |
| 6 |
Correct |
206 ms |
45608 KB |
Output is correct |
| 7 |
Correct |
180 ms |
45548 KB |
Output is correct |
| 8 |
Correct |
176 ms |
44016 KB |
Output is correct |
| 9 |
Correct |
197 ms |
45232 KB |
Output is correct |
| 10 |
Correct |
205 ms |
43748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5076 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
5012 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5076 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
5012 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5076 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
5012 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5076 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
5012 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
