Submission #1349258

#TimeUsernameProblemLanguageResultExecution timeMemory
1349258sash01Bitaro’s Party (JOI18_bitaro)C++20
14 / 100
2095 ms12852 KiB
#include <bits/stdc++.h>


using namespace std;

const int MAXN = 1e5;

int dp[MAXN + 5];
vector<int>graph[MAXN + 5];
bool used[MAXN + 5], is[MAXN + 5], canR[MAXN + 5];

void dfs(int node)
{
    used[node] = true;

    for(auto i: graph[node])
    {
        if(!used[i])dfs(i);
        if(canR[i])
        {
            canR[node] = true;
            dp[node] = max(dp[node], dp[i] + 1);
        }
    }
}

signed main()
{
    int n, m, q; cin >> n >> m >> q;

    for(int i = 1; i <= m; i++)
    {
        int x, y; cin >> x >> y;
        graph[x].push_back(y);
    }

    while(q--)
    {
        int t, s; cin >> t >> s;
        for(int i = 1; i <= s; i++)
        {
            int x; cin >> x;
            is[x] = true;
        }

        canR[t] = true;

        for(int i = 1; i <= n; i++)
        {
            if(!used[i] && i != t)
            {
                dfs(i);
            }
        }

        int ans = -1;
        for(int i = 1; i <= n; i++)
        {
            if(canR[i] && !is[i])
            {
                ans = max(ans, dp[i]);
            }
        }
        cout << ans << endl;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...