Submission #1345556

#TimeUsernameProblemLanguageResultExecution timeMemory
1345556thaibaotran555Bitaro’s Party (JOI18_bitaro)C++20
14 / 100
2092 ms13196 KiB
///TRAN THAI BAO :3

#include <iostream>
#include <cstdio>
#include <vector>
#include <deque>
#include <queue>

using namespace std;

#define maxN 200007
#define oo 2000000000

typedef pair<int, int> pii;

int n, m, q;
vector<int>adj[maxN];
vector<int>adj2[maxN];
int maxD[maxN];;
bool banned[maxN] = {false};
int cnt[maxN] = {0};

vector<int>order;

void readData()
{
    cin >> n >> m >> q;
    for(int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj2[v].push_back(u);
        cnt[u]++;
    }
    queue<int>q;
    for(int i = 1; i <= n; i++)
        if(cnt[i] == 0)
            q.push(i);
    while(!q.empty())
    {
        int u = q.front(), v;
        q.pop();
        order.push_back(u);
        for(int i = 0; i < adj2[u].size(); i++)
        {
            v = adj2[u][i];
            cnt[v]--;
            if(cnt[v] == 0)
                q.push(v);
        }
    }
}

void solveQuery()
{
    int root, k;
    cin >> root >> k;
    for(int i = 1; i <= n; i++)
    {
        maxD[i] = -oo;
        banned[i] = false;
    }
    for(int i = 0; i < k; i++)
    {
        int tmp;
        cin >> tmp;
        banned[tmp] = true;
    }
    maxD[root] = 0;
    for(int i = 0; i < order.size(); i++)
    {
        int u = order[i];
        if(maxD[u] == -oo)
            continue;
        for(int j = 0; j < adj2[u].size(); j++)
        {
            int v = adj2[u][j];
            maxD[v] = max(maxD[v], maxD[u]+1);
        }
    }
    int ans = -1;
    for(int i = 1; i <= n; i++)
        if(!banned[i])
            ans = max(ans, maxD[i]);
    cout << ans << '\n';
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    readData();
    while(q--)
        solveQuery();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...