QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#72297#5148. Tree Distancepaul2008WA 2ms22968kbC++142.9kb2023-01-15 12:47:432023-01-15 12:47:45

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-15 12:47:45]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:22968kb
  • [2023-01-15 12:47:43]
  • 提交

answer

#pragma GCC optimize(fast)
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
using namespace std;

const int N=2e5+5;

#define IT set<int>::iterator

int GC=0,Max_sz=0;
bool del[N];
int head[N],nex[N*2],w[N*2],to[N*2],indx=0;

void add_edge(int x,int y,int z)
{
	indx++;
	nex[indx]=head[x];
	to[indx]=y;
	w[indx]=z;
	head[x]=indx;
}

void add(int x,int y,int z)
{
	add_edge(x,y,z);
	add_edge(y,x,z);
}

int get_sz(int x,int fa)
{
	if(del[x])
		return 0;

	int ans=1;
	for(int i=head[x];i;i=nex[i])
	{
		int y=to[i];
		if(y!=fa)
			ans += get_sz(y,x);
	}
	return ans;
}

int dfs(int x,int fa,int tot) //返回子树sz
{
	if(del[x])
		return 0;

	int sum=1,Max=0;
	for(int i=head[x];i;i=nex[i])
	{
		int y=to[i];
		if(y!=fa)
		{
			int sz=dfs(y,x,tot);
			sum += sz;
			Max=max(Max,sz);
		}
	}
	Max=max(Max,tot-sum);

	if(Max<Max_sz)
		Max_sz=Max,GC=x;
	return sum;
}

int get_GC(int x)
{
	GC=0,Max_sz=0x3f3f3f3f;
	dfs(x,-1,get_sz(x,-1));
	return GC;
}

int cnt=0;
pair<long long,int> dist[N];
vector <pair <int,long long> > upd[N];
vector <pair <int,int> > que[N];
long long val[N],ans[N];

void get_dist(int x,int fa,long long nowdist)
{
	if(del[x])
		return;

	dist[++cnt]=make_pair(nowdist,x),val[x]=nowdist;
	for(int i=head[x];i;i=nex[i])
	{
		int y=to[i];
		if(y!=fa)
			get_dist(y,x,nowdist+w[i]);
	}
}

void getans(int x)
{
	if(del[x])
		return;

	x=get_GC(x),cnt=0;
	get_dist(x,-1,0);
	del[x]=true;

	sort(dist+1,dist+cnt+1);

	set <int> s;
	for(int i=1;i<=cnt;i++)
	{
		IT it=s.lower_bound(dist[i].second);
		if(it!=s.begin())
		{
			--it;
			int x=*it,y=dist[i].second;
			if(x>y)
				swap(x,y);
			upd[y].push_back(make_pair(x,val[x]+val[y]));
		}

		it=s.upper_bound(dist[i].second);
		if(it!=s.end())
		{
			int x=*it,y=dist[i].second;
			if(x>y)
				swap(x,y);
			upd[y].push_back(make_pair(x,val[x]+val[y]));
		}
		s.insert(dist[i].second);
	}

	for(int i=head[x];i;i=nex[i])
		getans(to[i]);
}

long long c[N];
int n;

void update(int x,long long y)
{
	for(int i=x;i;i-=i&-i)
		c[i]=min(c[i],y);
}

long long query(int x)
{
	long long ans=0x3f3f3f3f3f3f3f3f;
	for(int i=x;i<=n;i+=i&-i)
		ans=min(ans,c[i]);
	return ans;
}

int main()
{
	cin >> n;
	for(int i=1;i<n;i++)
	{
		int x,y,z;
		scanf("%d %d %d",&x,&y,&z);
		add(x,y,z);
	}

	getans(1);

	int T;
	cin >> T;
	for(int i=1;i<=T;i++)
	{
		int l,r;
		scanf("%d %d",&l,&r);
		que[r].push_back(make_pair(l,i));
	}

	memset(c,0x3f,sizeof(c));
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<upd[i].size();j++)
			update(upd[i][j].first,upd[i][j].second);

		for(int j=0;j<que[i].size();j++)
			ans[que[i][j].second]=query(que[i][j].first);
	}
	return 0;

	for(int i=1;i<=T;i++)
	{
		if(ans[i]==0x3f3f3f3f3f3f3f3f)
			printf("-1\n");
		else
			printf("%lld\n",ans[i]);
	}
	return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 22968kb

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:


result:

wrong answer Answer contains longer sequence [length = 5], but output contains 0 elements