Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
51573 AK2022071347 树上博弈 C++ 通过 100 605 MS 15888 KB 1935 2022-07-13 11:53:22

Tests(20/20):


/** * Given a tree, maintain the value from the root to each node. */ #include <cstdio> #include <cstdlib> #ifndef ONLINE_JUDGE #define FILEIO #endif // ONLINE_JUDGE #ifdef FILEIO FILE *infile=fopen("game.in","r"), *outfile=fopen("game.out","w"); #define scanf(x...) fscanf(infile,x) #define printf(x...) fprintf(outfile,x) #endif // FILEIO int n,m,a,b,c; struct Edge { int u,v,w; }edge[200000]; int head[100001],dfn[100001],sze[100001]; inline int add(int a,int b,int c) { static int tot=0; edge[++tot]=(Edge){head[a],b,c}; return head[a]=tot; } struct Node { Node* nxt; int dat; Node() { nxt=0x0; } }*rt[100001],*p; inline Node* addn(int k,int x) { if(!rt[k]) rt[k]=new Node; p=new Node; p->dat=x; p->nxt=rt[k]->nxt; return rt[k]->nxt=p; } void dfs(int k,int f=0) { static int cnt=0; dfn[k]=++cnt; sze[k]=1; while(head[k] and edge[head[k]].v==f) head[k]=edge[head[k]].u; for(register int j=head[k];j;j=edge[j].u) { if(edge[j].u and edge[edge[j].u].v==f) edge[j].u=edge[edge[j].u].u; dfs(edge[j].v,k); addn(edge[j].w,edge[j].v); sze[k]+=sze[edge[j].v]; } } inline int deal(int,int,int); int main() { scanf("%d",&n); for(register int i=1;i<n;++i) { scanf("%d%d%d",&a,&b,&c); add(a,b,c); } dfs(1); scanf("%d",&m); while(m--) { scanf("%d%d%d",&a,&b,&c); printf("%d\n",deal(a,b,c)); } #ifdef FILEIO fclose(infile); fclose(outfile); #undef scanf #undef printf #endif // FILEIO return 0; } inline bool check(int u,int v,int i) { if(!rt[i]) return false; p=rt[i]->nxt; bool res=false; int tmp; while(p) { tmp=p->dat; res^=((dfn[tmp]<=dfn[u] and dfn[u]<dfn[tmp]+sze[tmp]) xor (dfn[tmp]<=dfn[v] and dfn[v]<dfn[tmp]+sze[tmp])); p=p->nxt; } return res; } inline int deal(int u,int v,int r) { int res=0; for(register int i=r;i;--i) { if(check(u,v,i)) break; ++res; } return res; }


测评信息: