QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#72297 | #5148. Tree Distance | paul2008 | WA | 2ms | 22968kb | C++14 | 2.9kb | 2023-01-15 12:47:43 | 2023-01-15 12:47:45 |
Judging History
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