QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#570016 | #5148. Tree Distance | aaaaa | RE | 0ms | 0kb | C++20 | 2.4kb | 2024-09-17 13:15:49 | 2024-09-17 13:15:51 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=300010,M=1000010;
ll n,tot,first[N],nnext[N<<1],to[N<<1],w[N<<1],siz[N],f[N],root,s,a[N],cnt,vis[N],cntd;
ll dis[N],pp[N],ans[M];
set<ll>ss;
// vector<pair<ll,ll> >p[N];
unordered_map<ll, vector<pair<ll, ll>>> p;
struct sss {
ll x,y;
ll v;
bool operator<(sss b) {
return x<b.x;
}
} d[M*8];
void add(ll x,ll y,ll z) {
nnext[++tot]=first[x];
first[x]=tot;
to[tot]=y;
w[tot]=z;
}
void getroot(ll u,ll fa) {
siz[u]=1;
f[u]=0;
for(ll e=first[u]; e; e=nnext[e]) {
if(!vis[to[e]]&&to[e]!=fa) {
getroot(to[e],u);
siz[u]+=siz[to[e]];
f[u]=max(f[u],siz[to[e]]);
}
}
f[u]=max(f[u],s-siz[u]);
if(f[u]<f[root]) {
root=u;
}
}
void getdep(ll u,ll fa) {
a[++cnt]=u;
for(ll e=first[u]; e; e=nnext[e]) {
if(!vis[to[e]]&&to[e]!=fa) {
dis[to[e]]=dis[u]+w[e];
getdep(to[e],u);
}
}
}
void dfs(ll u) {
dis[u]=cnt=0;
vis[u]=1;
getdep(u,0);
sort(a+1,a+cnt+1,[](ll a,ll b) {
return dis[a]<dis[b];
});
ss.clear();
for(ll i=1; i<=cnt; i++) {
ss.insert(a[i]);
auto pos=ss.find(a[i]);
if(pos!=ss.begin()) {
pos--;
d[++cntd]= {*pos,a[i],dis[*pos]+dis[a[i]]};
pos++;
}
pos++;
if(pos!=ss.end()) {
d[++cntd]= {*pos,a[i],dis[*pos]+dis[a[i]]};
}
}
for(ll e=first[u]; e; e=nnext[e]) {
if(!vis[to[e]]) {
root=0;
s=siz[to[e]];
getroot(to[e],u);
dfs(root);
}
}
}
inline ll lowbit(ll x) {
return x&(-x);
}
inline void update(ll x,ll y) {
while(x<=n) {
pp[x]=min(pp[x],y);
x+=lowbit(x);
}
}
inline ll query(ll x) {
ll ans=1e18;
while(x>=1) {
ans=min(ans,pp[x]);
x-=lowbit(x);
}
return ans;
}
int main() {
ll now,a,b,c,q;
scanf("%d",&n);
for(ll i=1; i<=n-1; i++) {
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
f[0]=1e18;
s=n;
getroot(1,0);
dfs(root);
for(ll i=1; i<=cntd; i++) {
if(d[i].x>d[i].y) {
swap(d[i].x,d[i].y);
}
}
sort(d+1,d+cntd+1);
now=cntd;
scanf("%d",&q);
for(ll i=1; i<=q; i++) {
scanf("%d%d",&a,&b);
if(a>=b) {
ans[i]=-1;
continue;
}
p[a].push_back({b,i});
}
memset(pp,127,sizeof(pp));
for(ll i=n; i>=1; i--) {
while(d[now].x>=i) {
update(d[now].y,d[now].v);
now--;
}
for(auto j:p[i]) {
ans[j.second]=query(j.first);
}
}
for(ll i=1; i<=q; i++) {
printf("%lld\n",ans[i]);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
5 1 2 5 1 3 3 1 4 4 3 5 2 5 1 1 1 4 2 4 3 4 2 5