제출 #1349225

#제출 시각아이디문제언어결과실행 시간메모리
1349225boropotoBitaro’s Party (JOI18_bitaro)C++20
14 / 100
28 ms9312 KiB
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
void speed()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const int maxn=1e5+10;
int n,m,q,x,y;
int dp[maxn];
vector<int> v[maxn];
bool used[maxn],banned[maxn],can[maxn];
void read()
{
    cin>>n>>m>>q;
    int x1,y1;
    for(int i=1;i<=m;i++)
    {
        cin>>x1>>y1;
        v[x1].push_back(y1);
    }
    cin>>x>>y;
}
void dfs(int i)
{
    used[i]=1;
    if(i==x)
    {
        can[i]=1;
    }
    for(auto nb:v[i])
    {
        if(used[nb]==0)
        {
            dfs(nb);
        }
        if(can[nb]==1)
        {
            dp[i]=max(dp[i],dp[nb]+1);
            can[i]=1;
        }
    }
}
int main()
{
    speed();
    read();
    for(int i=x;i>=1;i--)
    {
        if(used[i]==0)
        {
            dfs(i);
        }
    }
    int node;
    for(int i=1;i<=y;i++)
    {
        cin>>node;
        banned[node]=1;
    }
    int ans=-1;
    for(int i=1;i<=x;i++)
    {
        if(banned[i]==1||can[i]==0)
        {
            continue;
        }
        ans=max(ans,dp[i]);
    }
    if(ans==0&&banned[x]==1)
    {
        cout<<-1<<endl;
        return 0;
    }
    cout<<ans<<endl;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...