CF45B-【School】题解

N_z_ · 2021-03-16 18:32:09 · 题解

前言

复杂度是玄学的，过是能过的。

思路

直接模拟就好了，注意到一个人只有一个朋友，直接热度减一就好了。

如果有人多次得到消息，那肯定是热度最大的一次最有效果（因为传播人数最多）。

同时只有第一次知道消息才计入答案。

代码

#include<bits/stdc++.h>
using namespace std;
int g[100001],v[100001],b[100001],nowthis[100001];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int x=1;x<=n;x++)
    cin>>g[x];
    for(int x=1;x<=m;x++)
    cin>>v[x];
    for(int x=1;x<=m;x++)
    cin>>b[x];
    int lastans=0;
    for(int x=1;x<=m;x++)
    {
        int ans=0;
        for(int y=(v[x]+lastans-1)%n+1;nowthis[y]<b[x];y=g[y])
        {
            if(nowthis[y]==0)ans++;
            nowthis[y]=b[x];
            b[x]--;
        }
        lastans=ans;
        cout<<ans<<endl;
    }
}