题解：P11280 「GFOI Round 2」Jom & Terry

liuchang09 · 2024-11-16 20:07:14 · 题解

思路

设 f(x) 为 x 节点到根节点的距离，若 f(x)\ <f(y) 则可以说明 x 节点比 y 节点前往根节点所需要的步数更少，又跟据题中所言：

如果 Terry 先移动到结点 u 后 Jom 在同一回合也移动到 u 是合法的

所以 f(x)\ =f(y) 的时候，则 Terry 和 Jom 在一路上紧追不舍但 Terry 更先到达根节点，而 Jom 紧随其后，此时仍然算 Terry 赢。

而 f(x)\ >f(y) 的时候，则 Jom 比 Terry 提前了至少一个回合到达根节点，所以 Jom 可以一直在根节点不移动然后等到 Terry 在到达与根节点直接相连的边的时候抓到他，此时 Jom 胜利。

解法

通过一遍广度优先搜索来记录 f(x) 的大小，随后通过 O(1) 时间复杂度回答。

总时间复杂度为 O(n+q) ，不加快读快写的话能极限时间过大的数据。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+1e1;
bool vis[maxn];
queue<int > q;
int n,m,root;
int f[maxn];
int t;
vector<int > a[maxn]; 
bool done[maxn];
int main(){
    memset(f,0x3f,sizeof f);
    printf("I'm here!\n");
    scanf("%d%d%d",&n,&m,&root);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        if(u==v) continue;
        a[u].push_back(v);
        a[v].push_back(u);//链接矩阵存双向边
    }
    q.push(root);
    vis[root]=true;
    f[root]=0;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=0;i<a[x].size();i++){
            int y=a[x][i];
            if(!vis[y]) q.push(y),f[y]=f[x]+1,vis[y]=true;
        }
    }
    scanf("%d",&t);
    while(t--){
        int x,y;
        scanf("%d%d",&x,&y);
        if(f[x]<=f[y])
            printf("Terry\n");
        else printf("Jom\n");
    }
    return 0;
}