QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#356321 | #8235. Top Cluster | USTC_fish_touching_team# | WA | 8ms | 114916kb | C++14 | 2.8kb | 2024-03-17 17:32:21 | 2024-03-17 17:32:21 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
const long long inf=1e15+1;
#define ll long long
vector<ll >d[N],id[N];
int sz[N];
int w[N];
int ton[N];
int mexall=0;
int vis[N];
int ans[N];
long long dep[N];
vector<int >p[N],vp[N];
int rt,siz,zqdx;
int wclsh;
void grt(int x,int fa){
sz[x]=1;
int szn=0;
for(int y:p[x])if(!vis[y]&&y!=fa){
grt(y,x);
sz[x]+=sz[y];
szn=max(szn,sz[y]);
}
szn=max(szn,zqdx-sz[x]);
if(siz>szn)siz=szn,rt=x;
}
void gx(int &x,int y){
x=min(x,y);
}
int t[N];
void add(int x,int y){
x=wclsh-x+1;
for(;x<=wclsh;x+=x&-x)t[x]=min(t[x],y);
}
int qr(int x){
x=wclsh-x+1;
int ans=1e9;
for(;x;x-=x&-x)ans=min(t[x],ans);
return ans;
}
ll cp[N],lsh[N];
void dfs(int x,int fa){
for(int i=0;i<p[x].size();i++)if(p[x][i]!=fa&&!vis[p[x][i]]){
int y=p[x][i];
dfs(y,x);
}
for(int i=0;i<d[x].size();i++){
gx(ans[id[x][i]],qr(cp[id[x][i]]));
}
}
void adfs(int x,int fa){
sz[x]=1;
for(int y:p[x])if(y!=fa&&!vis[y]){
adfs(y,x);sz[x]+=sz[y];
}
add(dep[x],w[x]);
}
void aadfs(int x,int fa){
for(int i=0;i<p[x].size();i++)if(p[x][i]!=fa&&!vis[p[x][i]]){
int y=p[x][i];
dep[y]=dep[x]+vp[x][i];
lsh[++lsh[0]]=dep[y];
aadfs(y,x);
}
for(int i=0;i<d[x].size();i++){
cp[id[x][i]]=d[x][i]-dep[x]+1;
lsh[++lsh[0]]=cp[id[x][i]];
}
}
void aaadfs(int x,int fa){
for(int i=0;i<p[x].size();i++)if(p[x][i]!=fa&&!vis[p[x][i]]){
int y=p[x][i];
dep[y]=lower_bound(lsh+1,lsh+1+wclsh,dep[y])-lsh;
aaadfs(y,x);
}
for(int i=0;i<d[x].size();i++){
cp[id[x][i]]=lower_bound(lsh+1,lsh+1+wclsh,cp[id[x][i]])-lsh;
}
}
void sol(int x,int dx){
if(vis[x])return ;
if(dx==1)return;
rt=0;
siz=1e9;
zqdx=dx;
grt(x,0);
x=rt;
aadfs(x,0);
sort(lsh+1,lsh+1+lsh[0]);
wclsh=unique(lsh+1,lsh+1+lsh[0])-lsh-1;
dep[x]=lower_bound(lsh+1,lsh+1+wclsh,dep[x])-lsh;
aaadfs(x,0);
for(int i=0;i<=wclsh;i++)t[i]=1e9;
add(dep[x],w[x]);
for(int i=0;i<p[x].size();i++)dfs(p[x][i],x),adfs(p[x][i],x);
for(int i=0;i<=wclsh;i++)t[i]=1e9;
add(dep[x],w[x]);
for(int i=(int)p[x].size()-1;i>=0;i--)dfs(p[x][i],x),adfs(p[x][i],x);
for(int i=0;i<d[x].size();i++){
gx(ans[id[x][i]],qr(cp[id[x][i]]));
}
for(int i=0;i<=wclsh;i++)t[i]=1e9;
vis[x]=1;
for(int y:p[x])sol(y,sz[y]);
}
int main(){
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++){
scanf("%d",&w[i]);
if(w[i]<=n)ton[w[i]]=1;
else w[i]=n+1;
}
while(ton[mexall])mexall++;
for(int i=1;i<n;i++){
int v,u,l;
scanf("%d%d%d",&u,&v,&l);
p[u].push_back(v);
vp[u].push_back(l);
p[v].push_back(u);
vp[v].push_back(l);
}
for(int i=1;i<=q;i++){
int x,k;
scanf("%d%d",&x,&k);
id[x].push_back(i);
d[x].push_back(k);
}
memset(ans,63,sizeof(ans));
sol(1,n);
for(int i=1;i<=q;i++){
printf("%d\n",min(mexall,ans[i]));
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 8ms
memory: 114916kb
input:
5 4 3 9 0 1 2 1 2 10 3 1 4 3 4 3 3 5 2 3 0 1 0 4 6 4 7
output:
0 0 3 4
result:
wrong answer 1st numbers differ - expected: '1', found: '0'