QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#373621 | #5148. Tree Distance | _violet_ | WA | 3ms | 41904kb | C++14 | 5.5kb | 2024-04-01 21:05:43 | 2024-04-01 21:05:45 |
Judging History
answer
//code by Emissary
#include<bits/stdc++.h>
#define fi first
#define se second
#define vc vector
#define db double
#define ll long long
#define mk make_pair
#define pb push_back
#define PI pair<int,int>
#define ull unsigned long long
#define err cerr << " -_- " << endl
#define debug cerr << " ------------------- " << endl
#define input(x) freopen(#x".in","r",stdin)
#define output(x) freopen(#x".out","w",stdout)
#define NO puts("No")
#define YES puts("Yes")
//#define int long long
using namespace std;
namespace IO{
inline int read(){
int X=0, W=0; char ch=getchar();
while(!isdigit(ch)) W|=ch=='-', ch=getchar();
while(isdigit(ch)) X=(X<<1)+(X<<3)+(ch^48), ch=getchar();
return W?-X:X;
}
inline void write(ll x){
if(x<0) x=-x, putchar('-');
if(x>9) write(x/10);
putchar(x%10+'0');
}
inline void sprint(ll x){write(x), putchar(32);}
inline void eprint(ll x){write(x), putchar(10);}
}using namespace IO;
const int MAXN = 1e6+5;
const ll inf = 1e18;
int n, q, siz[MAXN], all, Min, root, tot;
int head[MAXN], ne[MAXN<<1], to[MAXN<<1], weight[MAXN<<1], cnt;
ll ans[MAXN], maxn[MAXN<<2], dis[MAXN], tree[MAXN];
bool vis[MAXN];
struct Pairs{
int x, y; ll d;
inline bool friend operator < (const Pairs &x, const Pairs &y){
return x.y<y.y;
}
}Q[MAXN*13];
vc<PI> Qa[MAXN];
inline int lowbit(int x){return x & -x;}
inline void Add(int x, ll v){while(x) tree[x]=min(tree[x],v), x^=lowbit(x);}
inline ll Ask(int x){ll s=inf; while(x<=n) s=min(s,tree[x]), x+=lowbit(x); return s;}
inline void add(int x, int y, int w){++cnt;to[cnt]=y;ne[cnt]=head[x];head[x]=cnt;weight[cnt]=w;}
inline void pushup(int p){
maxn[p]=max(maxn[p<<1],maxn[p<<1|1]);
return ;
}
inline void build(int p, int l, int r){
if(l==r) return maxn[p]=-inf, void();
int mid=(l+r)>>1;
build(p<<1,l,mid); build(p<<1|1,mid+1,r);
return pushup(p);
}
inline void upd(int p, int l, int r, int pos, ll v){
if(l==r) return maxn[p]=v, void();
int mid=(l+r)>>1;
pos<=mid?upd(p<<1,l,mid,pos,v):upd(p<<1|1,mid+1,r,pos,v);
return pushup(p);
}
inline void getroot(int x, int f){
siz[x]=1; int maxn=0;
for(int i=head[x];i;i=ne[i]){
if(to[i]==f || vis[to[i]]) continue;
getroot(to[i],x); siz[x]+=siz[to[i]]; maxn=max(maxn,siz[to[i]]);
}
maxn=max(maxn,all-siz[x]);
if(maxn<Min) Min=maxn, root=x;
return ;
}
inline void findroot(int x, int s){
all=s;
Min=1e9; root=0;
return getroot(x,0);
}
inline void dfs(int x, int f){
siz[x]=1;
for(int i=head[x];i;i=ne[i]){
if(to[i]==f || vis[to[i]]) continue;
dis[to[i]]=dis[x]+weight[i]; dfs(to[i],x); siz[x]+=siz[to[i]];
}
if(f) Q[++tot]=Pairs{min(x,root),max(root,x),dis[x]}, upd(1,1,n,x,dis[x]);
return ;
}
inline void Add(int x, int f){
for(int i=head[x];i;i=ne[i]){
if(to[i]==f || vis[to[i]]) continue;
Add(to[i],x);
}
upd(1,1,n,x,dis[x]);
return ;
}
inline void Del(int x, int f){
for(int i=head[x];i;i=ne[i]){
if(to[i]==f || vis[to[i]]) continue;
Del(to[i],x);
}
upd(1,1,n,x,-inf);
return ;
}
inline int binary1(int p, int l, int r, int L, int R, ll v){
if(L>R) return 0;
if(L<=l && r<=R){
if(maxn[p]<v) return 0;
if(l==r){
if(maxn[p]>=v) return l;
return 0;
}
int mid=(l+r)>>1, c=0;
c=binary1(p<<1,l,mid,L,R,v);
if(c) return c;
return binary1(p<<1|1,mid+1,r,L,R,v);
}
int mid=(l+r)>>1, c=0;
if(L<=mid) c=binary1(p<<1,l,mid,L,R,v);
if(c) return c;
if(R>mid) c=binary1(p<<1|1,mid+1,r,L,R,v);
return c;
}
inline int binary2(int p, int l, int r, int L, int R, ll v){
if(L>R) return 0;
if(L<=l && r<=R){
if(maxn[p]<v) return 0;
if(l==r){
if(maxn[p]>=v) return l;
return 0;
}
int mid=(l+r)>>1, c=0;
c=binary2(p<<1|1,mid+1,r,L,R,v);
if(c) return c;
return c=binary2(p<<1,l,mid,L,R,v);
}
int mid=(l+r)>>1, c=0;
if(R>mid) c=binary2(p<<1|1,mid+1,r,L,R,v);
if(c) return c;
if(L<=mid) c=binary2(p<<1,l,mid,L,R,v);
return c;
}
inline void calc(int x, int f){
for(int i=head[x];i;i=ne[i]){
if(to[i]==f || vis[to[i]]) continue;
calc(to[i],x);
}
int p=binary1(1,1,n,x+1,n,dis[x]);
if(p) Q[++tot]=Pairs{x,p,dis[x]+dis[p]};
p=binary2(1,1,n,1,x-1,dis[x]);
if(p) Q[++tot]=Pairs{p,x,dis[x]+dis[p]};
return ;
}
inline void solve(int x){
vis[x]=1; dfs(x,dis[x]=0);
for(int i=head[x];i;i=ne[i]){
if(vis[to[i]]) continue;
Del(to[i],x); calc(to[i],x); Add(to[i],x);
}
for(int i=head[x];i;i=ne[i]){
if(vis[to[i]]) continue;
Del(to[i],x);
}
for(int i=head[x];i;i=ne[i]){
if(vis[to[i]]) continue;
findroot(to[i],siz[to[i]]); solve(root);
}
return ;
}
signed main(){
n=read();
//n=2e5;
for(int i=2;i<=n;++i){
int x, y, w;
x=read(), y=read(), w=read();
//x=i, y=rand()%(i-1)+1, w=rand()%1000000000+1;
add(x,y,w), add(y,x,w);
}
build(1,1,n); findroot(1,n); solve(root);
sort(Q+1,Q+1+tot); for(int i=1;i<=n;++i) tree[i]=inf;
cout << tot << endl;
//f(n>=1e5) return 0;
q=read();
for(int i=1;i<=q;++i){
int l, r;
l=read(), r=read();
Qa[r].pb(mk(l,i));
}
//for(int i=1;i<=tot;++i) cerr << "pairs:" << Q[i].x << ' ' << Q[i].y << ' ' << Q[i].d << endl;
int now=1;
for(int i=1;i<=n;++i){
while(now<=tot && Q[now].y==i){
Add(Q[now].x,Q[now].d);
++now;
}
for(auto j:Qa[i]) ans[j.se]=Ask(j.fi);
}
for(int i=1;i<=q;++i) eprint(ans[i]==inf?-1:ans[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 41904kb
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
output:
11 -1 3 7 7 2
result:
wrong answer 1st numbers differ - expected: '-1', found: '11'