当前位置: 首页 > 工具软件 > Go For It! > 使用案例 >

I - I Will Go

孙才捷
2023-12-01

GEMA is hosting Q rounds of 10-hour-long contests in honor of the great Danfto. Everybody wants to honor Danfto, but 10 hours is a really long time, so people are wondering whether to go or not.

A person’s decision is affected by their best friend’s decision. Each person has at most one best friend and there are no cycles (this is not a Disney movie and there are no reciprocated friendships), meaning that if Nicoleta’s best friend is Sancho and Sancho’s best friend is Teoo, Teoo’s best friend is not Sancho nor Nicoleta. In this case, Nicoleta will participate only if Sancho does, Sancho will participate only if Teoo does, and Teoo doesn’t have a best friend so he doesn’t depend on anyone.

People can also depend on some other factors like the weather, their mood or their mothers’ permission. So there’s no guarantee that they will participate even if their best friend does.

Now the rounds have passed and you are very curious about who were the brave souls that went to each round. You asked Tomaso if Teoo participated in a round, but Tomaso was drunk, so instead of replying yes or no, he told you that Nicoleta participated. You can deduce that Teoo went to the contest too because Nicoleta would only participate if Sancho did, which in turn would only go if Teoo did.

You asked Tomaso Q questions, one for each round, of whether y participated, and he told you that x did. Is it possible to know for sure if y participated in the round given that x did?

Input
The first line of the input contains two integers, N (2 ≤ N ≤ 1 × 105) and Q (1 ≤ Q ≤ 2 × 105), indicating the number of people invited to the Danfto honor rounds and the number of questions you asked Tomaso.

The next line contains N integers. The i-th integer ai (ai =  - 1 or 0 ≤ ai ≤ N - 1) indicates that the i-th person will only participate in a round if the ai-th person does. If a person doesn’t depend on anyone, ai is -1.

Q lines follow. The j-th line contains two integers xj and yj (0 ≤ xj, yj ≤ N - 1) indicating that you want to know if the yj-th person participated in the j-th round, and Tomaso told you that the xj-th person did.

Output
For each query, output “Yes” if you can determine that the y-th person participated and output “No” otherwise.

Example
Input
3 2
1 2 -1
0 2
2 0
Output
Yes
No

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn], tot;
int in[maxn], out[maxn];
vector<int>e[maxn];
void dfs(int u)
{
    in[u] = tot;
    for(int i = 0; i < (int)e[u].size(); i++)
    {
        tot++;
        int v = e[u][i];
        dfs(v);
    }
    out[u] = tot;
}
int main()
{
    int n, m, x, y;
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for(int i = 00; i < n; i++)
    {
        cin >> a[i];
        e[a[i] + 1].push_back(i+1);
    }
    dfs(0);
    for(int i = 0; i < m; i++)
    {
        cin >> x >> y;
        if(in[x+1] >= in[y+1] && in[x+1] <= out[y+1])
            printf("Yes\n");
        else
            printf("No\n");
    }
   
    return  0;
}

 类似资料: