Submission #1223072

#TimeUsernameProblemLanguageResultExecution timeMemory
1223072poatBitaro’s Party (JOI18_bitaro)C++17
7 / 100
2097 ms86632 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];
set<pair<int, int>> R[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++)
    {
        S[i].insert({0, i});
        R[i].insert({i, 0});
    }

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

    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 = 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...