Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
51843 zengjilin 树上博弈 C++ 运行超时 5 1000 MS 2168 KB 1077 2022-07-13 17:14:57

Tests(1/20):


#include <bits/stdc++.h> using namespace std; int n,f[100005],w[100005],s[100005]; int fa1[100005],fa2[100005]; int u,v,r,m; int father1(int x,int i) { i++; fa1[i]=f[x]; if(f[x]==0) return i; if(f[x]!=0) return father1(f[x],i); } int father2(int x,int i) { i++; fa2[i]=f[x]; if(f[x]==0) return i; if(f[x]!=0) return father2(f[x],i); } int main() { f[1]=0; scanf("%d",&n); for(int i=2; i<=n; i++) scanf("%d %d %d",&f[i],&v,&w[i]); scanf("%d",&m); for(int i=1; i<=m; i++) { s[100005]= {0}; scanf("%d %d %d",&u,&v,&r); if(u==v) { cout<<1; continue; } fa1[0]=u,fa2[0]=v; int f1=father1(u,0),f2=father2(v,0),j=0,k=0; for(j=0; j<f1; j++) { for(k=0; k<f2; k++) if(fa1[j]==fa2[k]) break; if(fa1[j]==fa2[k]) break; } for(int x=0; x<j; x++) s[x]=w[fa1[x]]; for(int x=j; x<j+k; x++) s[x]=w[fa2[x-j]]; int max=0; for(int x=0; x<j+k; x++) if(s[x]<=r&&s[x]>max) max=s[x]; printf("%d\n",r-max); } return 0; }


测评信息: