Submission #1269821

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269821		k12_khoi	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	2093 ms	12612 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;

const int N=2e5+5;
const int oo=1e9+1;

int n,m,request,x,y;
bool IsBusy[N];
vector <int> g[N];

namespace sub1
{
    int k;
    int a[N],dp[N];

    void dfs(int u)
    {
        if (!IsBusy[u]) dp[u]=0;
        else dp[u]=-oo;
        for (int v:g[u])
        {
            if (dp[v]==-1) dfs(v);

            dp[u]=max(dp[u],dp[v]+1);
        }
    }

    void solve()
    {
        while (request--)
        {
            cin >> x >> k;
            for (int j=1;j<=k;j++)
            {
                cin >> a[j];

                IsBusy[a[j]]=true;
            }

            for (int i=1;i<=n;i++)
            dp[i]=-1;

            dfs(x);

            if (dp[x]<0) dp[x]=-1;

            cout << dp[x] << '\n';


            for (int j=1;j<=k;j++)
            IsBusy[a[j]]=false;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m >> request;
    for (int i=1;i<=m;i++)
    {
        cin >> x >> y;
        g[y].push_back(x);

//        InDegree[x]++;
    }

    sub1::solve();
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 0 / 86