Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
51583 Cidoai 树上博弈 C++ 运行出错 0 1000 MS 145300 KB 2439 2022-07-13 11:54:01

Tests(0/20):


#include<cstdio> #include<cstring> using namespace std; const int N=100005; int n,m; struct node{ int to,nxt,w; }e[N<<1]; int head[N],cnt; int son[N]; inline void add(int u,int v,int w){ e[++cnt].to=v; e[cnt].nxt=head[u]; e[cnt].w=w; head[u]=cnt; } inline int max(int x,int y){ return x>y?x:y; } inline void swap(int &x,int &y){ int t=x; x=y; y=t; } int vis[N],f1,f2; int mp[N],nmp[N]; int now=1; int ru[N],rv[N],rw[N]; int lg[N]; int fa[N][18]; int dep[N]; inline void stmp(int f,int u){ nmp[now]=u; mp[u]=now++; son[mp[u]]=1; dep[mp[u]]=dep[mp[f]]+1; for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; if(v==f) continue; stmp(u,v); fa[mp[v]][0]=mp[u]; son[mp[u]]+=son[mp[v]]; } } inline int lca(int u,int v){ if(dep[u]>dep[v]) swap(u,v); for(int i=lg[n];i>=0;--i) if(dep[u]<=dep[fa[v][i]]) v=fa[v][i]; if(u==v) return u; for(int i=lg[n];i;--i) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i]; return fa[u][0]; } inline int dfsmaxn(int f,int u,int end,int lst){ if(dep[u]>=dep[end]||u==end) return 0; for(int i=head[nmp[u]];i;i=e[i].nxt){ int v=e[i].to; if(v==f) continue; return max(e[i].w<=lst?e[i].w:0,dfsmaxn(u,v,end,lst)); } } inline int dfsme(int f,int u,int end,int lst){ if(dep[u]>=dep[end]||u==end) return 0; for(int i=head[nmp[u]];i;i=e[i].nxt){ int v=e[i].to; if(v==f) continue; return max(e[i].w<=lst?(e[i].w&1?e[i].w:0):0,dfsme(u,v,end,lst)); } } int main(){ scanf("%d",&n); int u,v,w,r; lg[0]=-1; for(int i=1;i<n;++i){ lg[i]=lg[i>>1]+1; scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); ru[i]=u,rv[i]=v,rw[i]=w; if(vis[w]) f1=0; vis[w]=1; } lg[n]=lg[n>>1]+1; int root=1; dep[root]=1; stmp(0,root); memset(e,0,sizeof(e)); memset(head,0,sizeof(head)); cnt=0; for(int i=1;i<n;++i){ int u=mp[ru[i]],v=mp[rv[i]],w=w; add(u,v,w); add(v,u,w); } for(int i=1;i<=lg[n];++i) for(int j=1;j<=n;++j) fa[j][i]=fa[fa[j][i-1]][i-1]; scanf("%d",&m); while(m--){ scanf("%d%d%d",&u,&v,&r); u=mp[u],v=mp[v]; if(u>v) swap(u,v); if(f1||u==v){ printf("0\n"); continue; } int fst,sec; int fth=lca(u,v); fst=dfsmaxn(fa[fth][0],fth,u,r); fst=max(fst,dfsmaxn(fa[fth][0],fth,v,r)); fst=max(fst,r); sec=dfsme(fa[fth][0],fth,u,r); sec=max(sec,dfsme(fa[fth][0],fth,v,r)); printf("%d\n",fst-sec); } return 0; }


测评信息: