Submission #1223067

#TimeUsernameProblemLanguageResultExecution timeMemory
1223067poatBitaro’s Party (JOI18_bitaro)C++17
0 / 100
591 ms130692 KiB
// #pragma GCC optimize("Ofast")
// #pragma GCC target("popcnt")
 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
// #define double long double
#define mkp make_pair
 
#define txt freopen("shortcut.in", "r", stdin), freopen("shortcut.out", "w", stdout);
const int N = 2e5 + 100, K = 2000, inf = 1e16, mod = 1e9 + 7;
const double eps = 1e-6;

vector<int> gr[N];
set<pair<int, int>> S[N];

void solve()
{   
    int n, m, Q;
    cin >> n >> m >> Q;

    for(int i = m, a, b; i--;)
    {
        cin >> a >> b;
        gr[a].push_back(b);
    }

    for(int i = 1; i <= n; i++)
    {
        for(auto x : gr[i])
        {
            S[x].insert({1, i});
            for(auto j : S[i])
            {
                auto it = S[x].lower_bound(j);
                if(it != S[x].end() && *it == j)
                {
                    pair<int, int> p = *it;
                    S[x].erase(it);
                    p = max(p, {j.first + 1, j.second});
                    S[x].insert(p);
                } 
                else
                    S[x].insert({j.first + 1, j.second});
            }        
            while(S[x].size() > K)
                S[x].erase(S[x].begin());
        }
    }
    for(int i = 1; i <= n; i++)
        S[i].insert({0, i});

    for(int qq = Q, x, y; qq--;)
    {
        cin >> x >> y;

        if(y < K)
        {
            set<int> st;
            for(int it = y, f; it--;)
            {
                cin >> f;
                st.insert(f);
            }

            int mx = -1;
            for(auto i : S[x])
            {
                if(st.find(i.second) == st.end())
                    mx = max(mx, i.first);
            }

            cout << mx << "\n";
        }
        else   
            assert(0);
    }
}

signed main()
{   
    // txt;
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T = 1;
    for(; T--; solve());
}
/*
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...