1162 - Min Max Roads
PDF (English) Statistics Forum
Time Limit: 3 second(s) Memory Limit: 64 MB
You live in a Big country where there are many bi-directional roads connecting the cities. Since the people of the country are quite intelligent, they designed the country such that there is exactly one path to go from one city to another. A path consists of one or more connected roads.
Here cities are denoted by integers and each road has a cost of traveling. Now you are given the information about the Country. And you are given some queries, each consists of two cities. You have to find the shortest and longest road in the path from one city to another.
Input
Input starts with an integer T (≤ 5), denoting the number of test cases.
The first line of each case is a blank line. The next line contains n (2 ≤ n ≤ 105) denoting the number of cities. Then there will be n-1 lines containing three integers each. They will be given in the form u v w (1 ≤ u, v ≤ n, 0 < w ≤ 105, u ≠ v) meaning that there is a road between u and v and the cost of the road is w.
The next line contains an integer q (1 ≤ q ≤ 25000) denoting the number of queries. Each of the next q lines contains two integers x and y (1 ≤ x, y ≤ n, x ≠ y).
Output
For each case, print the case number in a single line. Then for each query x y, you should print one line containing the shortest and longest road along the path. See the samples for formatting.
Sample Input
Output for Sample Input
2
6
3 6 50
2 5 30
2 4 300
1 2 100
1 3 200
4
1 4
4 6
2 5
3 5
2
1 2 100
1
1 2
Case 1:
100 300
50 300
30 30
30 200
Case 2:
100 100
Note
Dataset is huge. Use faster i/o methods.
PROBLEM SETTER: JANE ALAM JAN
----------------------------------EDITORIAL=-------------------------------------------------------
HTTP://GAUTAMLCA.BLOGSPOT.IN/2016/04/1101-SECRET-MISSION-WEIGHT-OF-MAXIMUM.HTML
ABOVE EDITORIAL IS ENOUGH
-------------------------------------------------CODE-------------------------------------------------
-------------------------------------------------------------------------------------------------------------------------
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
vector<pair<pair<int,int> ,int> > v;
int dp_max[100010][25];
int dp_min[100010][25];
int dp_par[100010][25];
list<pair<int,int> > li[100010];
int lev[100010];
#define mp make_pair
int dfs(int start,int par,int l)
{
lev[start]=l;
list<pair<int,int> >:: iterator it;
for(it=li[start].begin();it!=li[start].end();it++)
{
if(it->first!=par)
{
lev[it->first]=l+1;
dp_par[it->first][0]=start;
dp_max[it->first][0]=it->second;
dp_min[it->first][0]=it->second;
dfs(it->first,start,l+1);
}
}
}
int binary_rais(int a,int b)// return lca of a,b
{
if(lev[a]<lev[b]) swap(a,b);
int lg;
for(lg=1;(1<<lg)<=lev[a];lg++);
lg--;
for(int i=lg;i>=0;i--)
{
if(lev[a]-(1<<i)>=lev[b])
{
a=dp_par[a][i];// moving a upward
}
}
if(a==b) return a;
else
{
for(int i=lg;i>=0;i--)
{
if(dp_par[a][i]!=-1 && dp_par[a][i]!=dp_par[b][i])// moving botha and b up
{
a=dp_par[a][i];
b=dp_par[b][i];
}
}
return dp_par[a][0];
}
}
int maximum(int a,int b,int par)
{
if(lev[a]<lev[b]) swap(a,b);
int lg;
for(lg=1;(1<<lg)<=lev[a];lg++);
lg--;
int ans=-1;
for(int i=lg;i>=0;i--)
{
if(lev[a]-(1<<i)>=lev[b])
{
if(ans<dp_max[a][i])
ans=dp_max[a][i];
a=dp_par[a][i];// moving a upward
}
}
// cout<<" after same base ans "<<ans<<endl;
if(a==b)
{
return ans;
}
else
{
for(int i=lg;i>=0;i--)
{
if(dp_par[a][i]!=-1 && dp_par[a][i]!=dp_par[b][i])// moving botha and b up
{
ans=max(ans,dp_max[a][i]);
ans=max(ans,dp_max[b][i]);
a=dp_par[a][i];
b=dp_par[b][i];
}
}
return max(ans,max(dp_max[a][0],dp_max[b][0]));
}
}
int minimum(int a,int b,int par)
{
if(lev[a]<lev[b]) swap(a,b);
int lg;
for(lg=1;(1<<lg)<=lev[a];lg++);
lg--;
int ans=INT_MAX;
for(int i=lg;i>=0;i--)
{
if(lev[a]-(1<<i)>=lev[b])
{
if(ans>dp_min[a][i])
ans=dp_min[a][i];
a=dp_par[a][i];// moving a upward
}
}
// cout<<" after same base ans "<<ans<<endl;
if(a==b)
{
return ans;
}
else
{
for(int i=lg;i>=0;i--)
{
if(dp_par[a][i]!=-1 && dp_par[a][i]!=dp_par[b][i])// moving botha and b up
{
ans=min(ans,dp_min[a][i]);
ans=min(ans,dp_min[b][i]);
a=dp_par[a][i];
b=dp_par[b][i];
}
}
return min(ans,min(dp_min[a][0],dp_min[b][0]));
}
}
int main()
{
//freopen("abc.txt","w",stdout);
int t;
cin>>t;
int cas=1;
while(t--)
{
cout<<"Case "<<cas++<<":"<<endl;
memset(dp_max,-1,sizeof dp_max);
memset(dp_par,-1,sizeof dp_par);
memset(dp_par,INT_MAX,sizeof dp_min);
memset(lev,0,sizeof lev);
for(int i=0;i<100010;i++)
{
li[i].clear();
}
int n,m;
scanf("%d",&n);
for(int i=0;i<n-1;i++)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
li[a].push_back({b,c});
li[b].push_back({a,c});
}
dp_par[1][0]=0;
dp_max[1][0]=0;
dp_min[1][0]=0;
dfs(1,0,1);
for(int height=1;height<25;height++)
{
for(int i=1;i<=n;i++)
{
if(dp_par[i][height-1]!=-1)
dp_par[i][height]=dp_par[dp_par[i][height-1]][height-1];
}
}
for(int height=1;height<25;height++)
{
for(int i=1;i<=n;i++)
{
if(dp_par[i][height-1]!=-1)
{
dp_max[i][height]=max(dp_max[dp_par[i][height-1]][height-1],dp_max[i][height-1]);
dp_min[i][height]=min(dp_min[dp_par[i][height-1]][height-1],dp_min[i][height-1]);
}
}
}
int q;
cin>>q;
while(q--)
{
int a,b;
scanf("%d %d",&a,&b);
if(a==b)
{
printf("0 0 \n");
}
else
{
int par=binary_rais(a,b);
printf("%d %d\n",minimum(a,b,par),maximum(a,b,par));
}
}
}
}
PDF (English) Statistics Forum
Time Limit: 3 second(s) Memory Limit: 64 MB
You live in a Big country where there are many bi-directional roads connecting the cities. Since the people of the country are quite intelligent, they designed the country such that there is exactly one path to go from one city to another. A path consists of one or more connected roads.
Here cities are denoted by integers and each road has a cost of traveling. Now you are given the information about the Country. And you are given some queries, each consists of two cities. You have to find the shortest and longest road in the path from one city to another.
Input
Input starts with an integer T (≤ 5), denoting the number of test cases.
The first line of each case is a blank line. The next line contains n (2 ≤ n ≤ 105) denoting the number of cities. Then there will be n-1 lines containing three integers each. They will be given in the form u v w (1 ≤ u, v ≤ n, 0 < w ≤ 105, u ≠ v) meaning that there is a road between u and v and the cost of the road is w.
The next line contains an integer q (1 ≤ q ≤ 25000) denoting the number of queries. Each of the next q lines contains two integers x and y (1 ≤ x, y ≤ n, x ≠ y).
Output
For each case, print the case number in a single line. Then for each query x y, you should print one line containing the shortest and longest road along the path. See the samples for formatting.
Sample Input
Output for Sample Input
2
6
3 6 50
2 5 30
2 4 300
1 2 100
1 3 200
4
1 4
4 6
2 5
3 5
2
1 2 100
1
1 2
Case 1:
100 300
50 300
30 30
30 200
Case 2:
100 100
Note
Dataset is huge. Use faster i/o methods.
PROBLEM SETTER: JANE ALAM JAN
----------------------------------EDITORIAL=-------------------------------------------------------
HTTP://GAUTAMLCA.BLOGSPOT.IN/2016/04/1101-SECRET-MISSION-WEIGHT-OF-MAXIMUM.HTML
ABOVE EDITORIAL IS ENOUGH
-------------------------------------------------CODE-------------------------------------------------
-------------------------------------------------------------------------------------------------------------------------
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
vector<pair<pair<int,int> ,int> > v;
int dp_max[100010][25];
int dp_min[100010][25];
int dp_par[100010][25];
list<pair<int,int> > li[100010];
int lev[100010];
#define mp make_pair
int dfs(int start,int par,int l)
{
lev[start]=l;
list<pair<int,int> >:: iterator it;
for(it=li[start].begin();it!=li[start].end();it++)
{
if(it->first!=par)
{
lev[it->first]=l+1;
dp_par[it->first][0]=start;
dp_max[it->first][0]=it->second;
dp_min[it->first][0]=it->second;
dfs(it->first,start,l+1);
}
}
}
int binary_rais(int a,int b)// return lca of a,b
{
if(lev[a]<lev[b]) swap(a,b);
int lg;
for(lg=1;(1<<lg)<=lev[a];lg++);
lg--;
for(int i=lg;i>=0;i--)
{
if(lev[a]-(1<<i)>=lev[b])
{
a=dp_par[a][i];// moving a upward
}
}
if(a==b) return a;
else
{
for(int i=lg;i>=0;i--)
{
if(dp_par[a][i]!=-1 && dp_par[a][i]!=dp_par[b][i])// moving botha and b up
{
a=dp_par[a][i];
b=dp_par[b][i];
}
}
return dp_par[a][0];
}
}
int maximum(int a,int b,int par)
{
if(lev[a]<lev[b]) swap(a,b);
int lg;
for(lg=1;(1<<lg)<=lev[a];lg++);
lg--;
int ans=-1;
for(int i=lg;i>=0;i--)
{
if(lev[a]-(1<<i)>=lev[b])
{
if(ans<dp_max[a][i])
ans=dp_max[a][i];
a=dp_par[a][i];// moving a upward
}
}
// cout<<" after same base ans "<<ans<<endl;
if(a==b)
{
return ans;
}
else
{
for(int i=lg;i>=0;i--)
{
if(dp_par[a][i]!=-1 && dp_par[a][i]!=dp_par[b][i])// moving botha and b up
{
ans=max(ans,dp_max[a][i]);
ans=max(ans,dp_max[b][i]);
a=dp_par[a][i];
b=dp_par[b][i];
}
}
return max(ans,max(dp_max[a][0],dp_max[b][0]));
}
}
int minimum(int a,int b,int par)
{
if(lev[a]<lev[b]) swap(a,b);
int lg;
for(lg=1;(1<<lg)<=lev[a];lg++);
lg--;
int ans=INT_MAX;
for(int i=lg;i>=0;i--)
{
if(lev[a]-(1<<i)>=lev[b])
{
if(ans>dp_min[a][i])
ans=dp_min[a][i];
a=dp_par[a][i];// moving a upward
}
}
// cout<<" after same base ans "<<ans<<endl;
if(a==b)
{
return ans;
}
else
{
for(int i=lg;i>=0;i--)
{
if(dp_par[a][i]!=-1 && dp_par[a][i]!=dp_par[b][i])// moving botha and b up
{
ans=min(ans,dp_min[a][i]);
ans=min(ans,dp_min[b][i]);
a=dp_par[a][i];
b=dp_par[b][i];
}
}
return min(ans,min(dp_min[a][0],dp_min[b][0]));
}
}
int main()
{
//freopen("abc.txt","w",stdout);
int t;
cin>>t;
int cas=1;
while(t--)
{
cout<<"Case "<<cas++<<":"<<endl;
memset(dp_max,-1,sizeof dp_max);
memset(dp_par,-1,sizeof dp_par);
memset(dp_par,INT_MAX,sizeof dp_min);
memset(lev,0,sizeof lev);
for(int i=0;i<100010;i++)
{
li[i].clear();
}
int n,m;
scanf("%d",&n);
for(int i=0;i<n-1;i++)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
li[a].push_back({b,c});
li[b].push_back({a,c});
}
dp_par[1][0]=0;
dp_max[1][0]=0;
dp_min[1][0]=0;
dfs(1,0,1);
for(int height=1;height<25;height++)
{
for(int i=1;i<=n;i++)
{
if(dp_par[i][height-1]!=-1)
dp_par[i][height]=dp_par[dp_par[i][height-1]][height-1];
}
}
for(int height=1;height<25;height++)
{
for(int i=1;i<=n;i++)
{
if(dp_par[i][height-1]!=-1)
{
dp_max[i][height]=max(dp_max[dp_par[i][height-1]][height-1],dp_max[i][height-1]);
dp_min[i][height]=min(dp_min[dp_par[i][height-1]][height-1],dp_min[i][height-1]);
}
}
}
int q;
cin>>q;
while(q--)
{
int a,b;
scanf("%d %d",&a,&b);
if(a==b)
{
printf("0 0 \n");
}
else
{
int par=binary_rais(a,b);
printf("%d %d\n",minimum(a,b,par),maximum(a,b,par));
}
}
}
}
No comments:
Post a Comment