LUBENICA - Lubenica

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/lubenica


Mạng lưới giao thông ở 1 nước bao gồm N thành phố (đánh số từ 1 đến N) và N-1 đường nối các thành phố với nhau. Có một đường đi duy nhất giữa mỗi cặp thành phố. Mỗi con đường có một độ dài xác định.

Viết chương trình, với mỗi K cặp thành phố cho trước, tìm độ dài của con đường ngắn nhất và dài nhất trên đường đi giữa 2 thành phố này.

Dữ liệu

Dòng đầu tiên chứa số nguyên N, 2 ≤ N ≤ 100 000.

Mỗi dòng trong số N-1 dòng tiếp theo chứa 3 số nguyên A, B, C cho biết có một con đường độ dài C giữa thành phố A và thành phố B. Độ dài của mỗi con đường là số nguyên dương không vượt quá 1000000.

Dòng tiếp theo chứa số nguyên K, 1 ≤ K ≤ 100 000.

Mỗi dòng trong số K dòng tiếp theo chứa 2 số nguyên D và E - chỉ số của 2 thành phố cần truy vấn.

Kết qủa

Mỗi dòng trong số K dòng chứa 2 số nguyên - độ dài của con đường ngắn nhất và dài nhất trên đường nối giữa 2 thành phố tương ứng.

Ví dụ

Dữ liệu:
5
2 3 100
4 3 200
1 5 150
1 3 50
3
2 4
3 5
1 2
Kết qủa
100 200
50 150
50 100

Dữ liệu:
7
3 6 4
1 7 1
1 3 2
1 2 6
2 5 4
2 4 4
5
6 4
7 6
1 2
1 3
3 5

Kết qủa
2 6
1 4
6 6
2 2
2 6

Dữ liệu:
9
1 2 2
2 3 1
3 4 5
2 7 4
1 5 3
5 6 1
5 9 2
1 8 3
5
6 9
7 8
9 4
1 2
7 3

Kết qủa
1 2
2 4
1 5
2 2
1 4

Được gửi lên bởi:Jimmy
Ngày:2007-12-18
Thời gian chạy:1.210s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Croatian OI 2006

hide comments
2021-05-27 18:02:06
Tham khảo: https://vnspoj.github.io/problems/LUBENICA
2019-12-24 16:09:47
LCA
CLQD K12
2019-11-07 02:42:42
#include <bits/stdc++.h>

using namespace std;
int n,m,d[100001][20],b[100001][20],c[100001][20],pa[100001],h[100001];
bool f[100001];
vector < vector <int> > a(100001),a1(100001);
void dfs(int u)
{
f[u]=false;
for(int i=0;i<a[u].size();i++)
if(f[a[u][i]]==true)
{
b[a[u][i]][0]=a1[u][i];
c[a[u][i]][0]=a1[u][i];
pa[a[u][i]]=u;
h[a[u][i]]=h[u]+1;
dfs(a[u][i]);
}
}
int lca(int x,int y)
{
int kq1,kq2;
kq1=1e9;
kq2=1e9;
if(h[x]>h[y]) swap(x,y);
if(h[x]!=h[y])
for(int i=17;i>=0;i--)
if(h[d[y][i]]>=h[x])
{
kq1=min(kq1,b[y][i]);
y=d[y][i];
}
if(x==y) return kq1;
for(int i=17;i>=0;i--)
while(d[x][i]!=d[y][i])
{
kq1=min(kq1,b[y][i]);
kq2=min(kq2,b[x][i]);
x=d[x][i];
y=d[y][i];
}
kq1=min(kq1,b[y][0]);
kq2=min(kq2,b[x][0]);
return min(kq1,kq2);
}
int lca2(int x,int y)
{
int kq1,kq2;
kq1=0;
kq2=0;
if(h[x]>h[y]) swap(x,y);
if(h[x]!=h[y])
for(int i=17;i>=0;i--)
if(h[d[y][i]]>=h[x])
{
kq1=max(kq1,c[y][i]);
y=d[y][i];
}
if(x==y) return kq1;
for(int i=17;i>=0;i--)
while(d[x][i]!=d[y][i])
{
kq1=max(kq1,c[y][i]);
kq2=max(kq2,c[x][i]);
x=d[x][i];
y=d[y][i];
}
kq1=max(kq1,c[y][0]);
kq2=max(kq2,c[x][0]);
return max(kq1,kq2);
}
int main()
{
cin >> n;
for(int i=1;i<n;i++)
{
int x,y,z;
cin >> x >> y >> z;
a[x].push_back(y);
a[y].push_back(x);
a1[x].push_back(z);
a1[y].push_back(z);
f[i]=true;
}
f[n]=true;
h[1]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=17;j++)
{
b[i][j]=1e9;
c[i][j]=0;
}
dfs(1);
for(int i=1;i<=n;i++) d[i][0]=pa[i];
for(int j=1;j<=17;j++)
for(int i=1;i<=n;i++)
{
d[i][j]=d[d[i][j-1]][j-1];
}
for(int j=1;j<=17;j++)
for(int i=1;i<=n;i++)
{
b[i][j]=min(b[i][j-1],b[d[i][j-1]][j-1]);
c[i][j]=max(c[i][j-1],c[d[i][j-1]][j-1]);
}
cin >> m;
for(int i=1;i<=m;i++)
{
int x,y;
cin >> x >> y;
int k=lca(x,y);
int k2=lca2(x,y);
cout << k <<" "<< k2 << endl;
}
return 0;
}
2018-12-17 10:58:01
làm lại 1 đấm AC với LCA chạy lâu hơn 0.10 và tốn mem hơn HLD
frostpixel aka.How 2 AC
2018-11-18 15:12:54
First time tự đọc và cài HLD để rồi AC chỉ với 0.53 s ( trong đầu cứ nghĩ là dùng HLD thay vì LCA thường sẽ bị TLE ), một cảm giác thật là high ^_^ :))
2018-09-09 16:47:25
Bạn nào muốn tham khảo thì đây nha :v
http://bit.ly/2H6N2zl

Last edit: 2019-01-11 17:19:38
2018-06-17 08:55:21
code AC :https://bit.ly/2HSOTD3
2018-02-01 14:37:10
easy
2018-01-02 03:24:48
HLD 1 đấm AC
frostpixel aka.How 2 AC
2018-01-01 12:19:14
tao trâu cũng AC :))
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.