QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#373621#5148. Tree Distance_violet_WA 3ms41904kbC++145.5kb2024-04-01 21:05:432024-04-01 21:05:45

Judging History

你现在查看的是最新测评结果

  • [2024-04-01 21:05:45]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:41904kb
  • [2024-04-01 21:05:43]
  • 提交

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'