QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#72506#5148. Tree DistanceJinTianHaoWA 808ms91052kbC++173.1kb2023-01-16 13:36:502023-01-16 13:36:53

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-16 13:36:53]
  • 评测
  • 测评结果:WA
  • 用时:808ms
  • 内存:91052kb
  • [2023-01-16 13:36:50]
  • 提交

answer

#include <bits/stdc++.h>
#define inf 1000000007
#define mod 1000000007
#define lowbit(x) (x&(-x))
#define int long long
// #pragma GCC optimize("Ofast","inline","-ffast-math")
// #pragma GCC target("avx,sse2,sse3,sse4,mmx")
using namespace std;
template <typename T> void read(T &x){
	x=0;char ch=getchar();int fh=1;
	while (ch<'0'||ch>'9'){if (ch=='-')fh=-1;ch=getchar();}
	while (ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	x*=fh;
}
template <typename T> void write(T x) {
	if (x<0) x=-x,putchar('-');
	if (x>9) write(x/10);
	putchar(x%10+'0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int n,q,rt,all,tot;
int h[200005],e[400005],w[400005],ne[400005],idx;
int siz[200005],maxp[200005];
int dist[200005],bit[200005],ans[1000005];
bool vis[200005];
struct node
{
	int l,r,dist;
	bool operator<(const node &o) const
	{
		return l>o.l;
	}
}opr[1000005];
struct query
{
	int l,r,id;
	bool operator<(const query &o) const
	{
		return l>o.l;
	}
}qry[1000005];
void change(int x,int y)
{
	while(x<=n)
	{
		bit[x]=min(bit[x],y);
		x+=lowbit(x);
	}
}
int ask(int x)
{
	int res=1ll*inf*inf;
	while(x)
	{
		res=min(res,bit[x]);
		x-=lowbit(x);
	}
	return res;
}
void getrt(int x,int fa)
{
	siz[x]=1;maxp[x]=0;
	for(int i=h[x];~i;i=ne[i])
	{
		int j=e[i];
		if(j==fa||vis[j]) continue;
		getrt(j,x);siz[x]+=siz[j];
		maxp[x]=max(maxp[x],siz[j]);
	}
	maxp[x]=max(maxp[x],all-siz[x]);
	if(maxp[rt]>maxp[x]) rt=x;
}
void add(int a,int b,int c)
{
	e[idx]=b,w[idx]=c;ne[idx]=h[a],h[a]=idx++;
}
pair<int,int> d[1000005];
int len;
void dfs(int x,int fa,int dis)
{
	d[++len]={dis,x};dist[x]=dis;
	for(int i=h[x];~i;i=ne[i])
	{
		int j=e[i];
		if(j==fa||vis[j]) continue;
		dfs(j,x,dis+w[i]);
	}
}
void solve(int x)
{
	len=1;d[1]={0,x};dist[x]=0;
	for(int i=h[x];~i;i=ne[i])
	{
		int j=e[i];
		if(vis[j]) continue;
		dfs(j,x,w[i]);
	}
	sort(d+1,d+len+1);
	set<int> st={-inf,inf};
	for(int i=1;i<=len;++i)
	{
		int pre=*prev(st.lower_bound(d[i].second));
		if(pre!=-inf)
			opr[++tot]={pre,d[i].second,dist[d[i].second]+dist[pre]};
		int suf=*st.lower_bound(d[i].second);
		if(suf!=inf)
			opr[++tot]={d[i].second,suf,dist[d[i].second]+dist[suf]};
		st.insert(d[i].second);
	}
}
void divide(int x)
{
	vis[x]=1;
	solve(x);
	for(int i=h[x];~i;i=ne[i])
	{
		int j=e[i];
		if(vis[j]) continue;
		maxp[rt=0]=all=siz[j];
		getrt(j,0);getrt(rt,0);
		divide(rt);
	}
}
signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(n);memset(h,-1,sizeof(h));
	memset(bit,0x3f,sizeof(bit));
	for(int i=1;i<n;++i)
	{
		int a,b,c;
		read(a);read(b);read(c);
		add(a,b,c);add(b,a,c);
	}
	maxp[rt=0]=all=n;
	getrt(1,0);getrt(rt,0);
	divide(rt);
	sort(opr+1,opr+tot+1);
	read(q);
	for(int i=1;i<=q;++i)
		read(qry[i].l),read(qry[i].r),qry[i].id=i;
	sort(qry+1,qry+q+1);
	for(int i=1,j=1;i<=q;++i)
	{
		while(j<=tot&&opr[j].l>=qry[i].l)
			change(opr[j].r,opr[j].dist),++j;
		ans[qry[i].id]=ask(qry[i].r);
	}
	for(int i=1;i<=q;++i)
	{
		if(ans[i]>1ll*inf*inf/2) ans[i]=-1;
		writeln(ans[i]);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 20200kb

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:

-1
3
7
7
2

result:

ok 5 number(s): "-1 3 7 7 2"

Test #2:

score: -100
Wrong Answer
time: 808ms
memory: 91052kb

input:

199999
31581 23211 322548833
176307 196803 690953895
34430 82902 340232856
36716 77480 466375266
7512 88480 197594480
95680 61864 679567992
19572 14126 599247796
188006 110716 817477802
160165 184035 722372640
23173 188594 490365246
54801 56250 304741654
10103 45884 643490340
127469 154479 214399361...

output:

62626888
5166547250
23073
3329219
55723
2037249435
5166547250
498563340
823009547
398008279281
5166547250
3403101
1777854
1777854
34251
1309202503
164724496
2037249435
167913379
34251
28320304
1902761
3329219
5166547250
25247086
209097
5166547250
539416167
355742190
28320304
2514272
5166547250
47002...

result:

wrong answer 1st numbers differ - expected: '29573323', found: '62626888'