#include "swap.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//ifstream cin("a.in");
//ofstream cout("a.out");
vector<pair<int,pair<int,int> > >edges;
bool cmp(pair<int,pair<int,int> >a,pair<int,pair<int,int> >b)
{
return a.first<b.first;
}
vector<pair<int,long long> >adj[200005];
vector<long long>vec;
long long rasp[200005];
long long jos[200005];
long long sus[200005];
long long lvl[200005];
long long inf=1e14;
void dfs(int curr,int parent)
{
int i,k;
lvl[curr]=lvl[parent]+1;
vec.clear();
if(adj[curr].size()>=3)
{
for(i=0; i<adj[curr].size(); i++)
{
vec.push_back(adj[curr][i].second);
}
sort(vec.begin(),vec.end());
jos[curr]=vec[2];
}
else
{
jos[curr]=inf;
}
for(i=0; i<adj[curr].size(); i++)
{
k=adj[curr][i].first;
if(k!=parent)
{
dfs(k,curr);
}
jos[curr]=min(jos[curr],max(jos[curr],adj[curr][i].second));
}
}
void dfs2(int curr,int par,long long val)
{
int i,k;
sus[curr]=max(min(jos[par],sus[par]),val);
rasp[curr]=min(sus[curr],jos[curr]);
for(i=0; i<adj[curr].size(); i++)
{
k=adj[curr][i].first;
if(k!=par)
{
dfs2(k,curr,adj[curr][i].second);
}
}
}
///bl e parinte
/// drum e cost de a merge la parinte
/// ext e cost minim degreee 3
long long bl[30][200005];
long long ext[30][200005];
long long drum[30][200005];
void dfs3(int curr,int par,long long val)
{
int i,k;
bl[0][curr]=par;
ext[0][curr]=rasp[curr];
drum[0][curr]=val;
for(i=1; i<=30; i++)
{
bl[i][curr]=bl[i-1][bl[i-1][curr]];
ext[i][curr]=min(ext[i-1][curr],ext[i-1][bl[i-1][curr]]);
drum[i][curr]=max(drum[i-1][curr],drum[i-1][bl[i-1][curr]]);
}
for(i=0; i<adj[curr].size(); i++)
{
k=adj[curr][i].first;
if(k!=par)
{
dfs3(k,curr,adj[curr][i].second);
}
}
}
int lca (int a,int b)
{
int i,curr;
if(lvl[a]<lvl[b])
{
swap(a,b);
}
for(i=30; i>=0; i--)
{
curr=bl[i][a];
if(lvl[curr]>=lvl[b])
{
a=curr;
}
}
if(a==b)
{
return a;
}
else
{
for(i=30; i>=0; i--)
{
if(bl[i][a]!=bl[i][b])
{
a=bl[i][a];
b=bl[i][b];
}
}
return bl[0][a];
}
}
pair<long long,long long> calc (int a,int b)
{
long long curr,maxdrum=0,minrel=inf,i;
for(i=30; i>=0; i--)
{
curr=bl[i][a];
if(lvl[curr]>=lvl[b])
{
maxdrum=max(maxdrum,drum[i][a]);
minrel=min(minrel,ext[i][a]);
a=curr;
}
}
return make_pair(maxdrum,minrel);
}
void init(int n, int m,vector<int> a, vector<int> b, vector<int> w)
{
int i;
for(i=1; i<=m; i++)
{
a[i-1]++;
b[i-1]++;
adj[a[i-1]].push_back({b[i-1],w[i-1]});
adj[b[i-1]].push_back({a[i-1],w[i-1]});
// edges.push_back({w[i-1],{a[i-1],b[i-1]}});
}
// sort(edges.begin(),edges.end(),cmp);
sus[0]=inf;
jos[0]=inf;
dfs(1,0);
dfs2(1,0,0);
dfs3(1,0,0);
}
int getMinimumFuelCapacity(int x, int y)
{
int lc;
x++;
y++;
pair<long long,long long>a;
pair<long long,long long>b;
lc=lca(x,y);
a=calc(x,lc);
b=calc(y,lc);
a.first=max(a.first,b.first);
a.second=min(a.second,b.second);
a.first=max(a.first,b.second);
if(a.first==inf)
{
return -1;
}
else
{
return a.first;
}
}
/*int main()
{
int N, M;
cin>>N>>M;
vector<int> U(M), V(M), W(M);
for (int i = 0; i < M; ++i)
{
cin>>U[i]>>V[i]>>W[i];
}
int Q;
cin>>Q;
vector<int> X(Q), Y(Q);
for (int i = 0; i < Q; ++i)
{
cin>>X[i]>>Y[i];
}
init(N, M, U, V, W);
vector<int> minimum_fuel_capacities(Q);
for (int i = 0; i < Q; ++i)
{
minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
}
for (int i = 0; i < Q; ++i)
{
cout<<minimum_fuel_capacities[i];
}
return 0;
}
*/
Compilation message
swap.cpp: In function 'void dfs(int, int)':
swap.cpp:27:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for(i=0; i<adj[curr].size(); i++)
| ~^~~~~~~~~~~~~~~~~
swap.cpp:38:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for(i=0; i<adj[curr].size(); i++)
| ~^~~~~~~~~~~~~~~~~
swap.cpp: In function 'void dfs2(int, int, long long int)':
swap.cpp:53:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(i=0; i<adj[curr].size(); i++)
| ~^~~~~~~~~~~~~~~~~
swap.cpp: In function 'void dfs3(int, int, long long int)':
swap.cpp:80:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(i=0; i<adj[curr].size(); i++)
| ~^~~~~~~~~~~~~~~~~
swap.cpp:78:39: warning: iteration 29 invokes undefined behavior [-Waggressive-loop-optimizations]
78 | drum[i][curr]=max(drum[i-1][curr],drum[i-1][bl[i-1][curr]]);
| ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
swap.cpp:74:15: note: within this loop
74 | for(i=1; i<=30; i++)
| ~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5588 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5648 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5588 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5648 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5588 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5648 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5588 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5648 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5588 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5648 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5588 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5648 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
