社区讨论

dalao为甚会RE

P1600[NOIP 2016 提高组] 天天爱跑步参与者 7已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@mi6lhfms
此快照首次捕获于
2025/11/20 06:49
4 个月前
此快照最后确认于
2025/11/20 06:49
4 个月前
查看原帖
dfs
CPP
#include <iostream>
#include <cstring>
using namespace std;
bool vis[101010],flag;
long long a[101010],ans[101010],map[10101][10101],u,v,n,m;
void dfs(long long s,long long e,long long t)
{
    if(flag) return;
    if(vis[s]) return;//cout<<st<<" "<<t<<endl;
    vis[s]=1;
    if(s==e)//if(a[ed]==t) ans[ed]++;
        flag=1;
    if(a[s]==t) ans[s]++;
    for(long long i=1;i<=n;i++)
        if(map[s][i] && !vis[i])
            dfs(i,e,t+1);
}
int main()
{
    cin>>n>>m;
    for(long long i=1;i<n;i++)
    {
        cin>>u>>v;
        map[u][v]=1;
        map[v][u]=1;
    }
    for(long long i=1;i<=n;i++) 
        cin>>a[i];
    for(long long i=1;i<=m;i++)
    {
        memset(vis,0,sizeof(vis));
        flag=0;long long s,e;
        cin>>s>>e;
        dfs(s,e,0);
    }
    for(long long i=1;i<=n;i++) cout<<ans[i]<<" ";
    return 0;
}
/* 6 3 2 3 1 2 1 4 4 5 4 6 0 2 5 1 2 3
1 5 1 3 2 6 */ /* 5 3 1 2 2 3 2 4 1 5 0 1 0 3 0
3 1 1 4 5 5 */

回复

6 条回复,欢迎继续交流。

正在加载回复...