Submission #1349622

#TimeUsernameProblemLanguageResultExecution timeMemory
1349622boropotoBitaro’s Party (JOI18_bitaro)C++20
14 / 100
2097 ms168548 KiB
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int MAXN = 1e5;
const int block = 117;

int n, m, q, x, y, dp[MAXN + 5], mx[MAXN + 5];
vector<pair<int,int>>vals[MAXN + 5];
vector<int>v[MAXN + 5], v1[MAXN + 5];
bool used[MAXN + 5], is[MAXN + 5], canR[MAXN + 5], vis[MAXN + 5];

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

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

void solve1()
{
    for(int i = 1; i <= n; i++)
    {
        used[i] = false;
        is[i] = false;
        dp[i] = 0;
        canR[i] = false;
    }
    for(int i = 1; i <= y; i++)
    {
        int a; cin >> a;
        is[a] = true;
    }

    canR[x] = true;

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

    int ans = -1;
    for(int i = 1; i <= n; i++)
    {
        if(canR[i] && !is[i])
        {
            ans = max(ans, dp[i]);
        }
    }
    cout << ans << endl;
}
void dfs(int node)
{
    vis[node] = true;
    vector<int>ve;
    ve.push_back(node);
    mx[node] = 0;

    for(auto i: v1[node])
    {
        if(!vis[i])
            dfs(i);

        for(auto j: vals[i])
        {
            ve.push_back(j.second);
            mx[j.second] = max(mx[j.second], j.first + 1);
        }

    }

    sort(ve.begin(), ve.end());

    vals[node].push_back({mx[ve[0]], ve[0]});
    mx[ve[0]] = -1;

    for(int i = 1; i < ve.size(); i++)
    {
        if(ve[i] != ve[i - 1])
        {
            vals[node].push_back({mx[ve[i]], ve[i]});
            mx[ve[i]] = -1;
        }
    }

    sort(vals[node].rbegin(), vals[node].rend());
    while(vals[node].size() > block)vals[node].pop_back();
}

void solve2()
{
    for(int i = 1; i <= n; i++)
        is[i] = false;

    for(int i = 1; i <= y; i++)
    {
        int a; cin >> a;
        is[a] = true;
    }

    int ptr = 0;
    while(ptr < vals[x].size() && is[vals[x][ptr].second])ptr++;

    if(ptr == vals[x].size())cout << -1 << endl;
    else cout << vals[x][ptr].first << endl;
}

signed main()
{
    cin >> n >> m >> q;
    for(int i = 1; i <= m; i++)
    {
        int x, y; cin >> x >> y;
        v[x].push_back(y);
        v1[y].push_back(x);
    }

    for(int i = 1; i <= n; i++)
        if(vals[i].empty())dfs(i);

    while(q--)
    {
        cin >> x >> y;

        if(y >= block)
            solve1();
        else
            solve2();
    }

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...