Submission #1229111

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229111		acoatoitgs	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	0 ms	324 KiB

bitaro

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

#define ll long long
#define pb push_back
#define m_pi 2 * acos(0.0)
#define all(a) (a).begin(), (a).end()
#define LL_INF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
void solve();

constexpr bool isTc = 0;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    if (isTc)
    {
        int T;
        cin >> T;
        while (T--)
        {
            solve();
        }
    }
    else
        solve();
    return 0;
}

/*######################################*/

ll N, M, Q;
vector<vector<ll>> adj;
vector<set<pair<ll,ll>, greater<pair<ll,ll>>>> pq;
vector<unordered_map<ll,ll>> mp;



void solve()
{
    cin >> N >> M >> Q;

    adj.resize(N);
    pq.resize(N);
    mp.resize(N);

    for(ll i = 0; i < M; i++)
    {
        ll a,b;
        cin >> a >> b, --a, --b;
        adj[a].emplace_back(b);
    }
    constexpr ll SQRT = 315;
    //precompute
    for(ll i = 0; i < N; i++)
    {
        pq[i].insert({0, i});
        mp[i][i] = 0;

        for(auto ed : adj[i])
        {
            for(auto [d, e] : pq[i])
            {
                if(mp[ed].find(e) != mp[ed].end())
                {
                    if(mp[ed][e] < d+1) 
                    {
                        pq[ed].erase({mp[ed][e], e});
                        pq[ed].insert({d+1, e});
                        mp[ed][e] = d+1;
                    }
                    continue;
                }

                if(pq[ed].size() >= SQRT)
                {
                    if((*pq[ed].rbegin()).first < d+1)
                    {
                        mp[ed].erase((*pq[ed].rbegin()).second);
                        pq[ed].erase(*pq[ed].rbegin());
                    }
                    else continue;
                }

                pq[ed].insert({d+1, e});
                mp[ed][e] = d+1;
            }
        }

    }
    
    while(Q--)
    {
        ll T, Y;
        cin >> T >> Y;
        --T;
        unordered_set<ll> P;
        ll x;
        for(ll i = 0; i < Y; i++)
        {
            cin >> x;
            P.insert(--x);
        }

        if(Y >= SQRT)
        {
            vector<ll> dp(N, -1);
            for(ll i = 0; i <= T; i++)
            {
                if(!P.count(i)) dp[i] = max(dp[i], 0ll);
                if(dp[i] != -1)
                {
                    for(auto e : adj[i])
                    {
                        dp[e] = max(dp[e], dp[i]+1);
                    }
                }
            }

            cout << dp[T] << "\n";
        }
        else
        {
            bool b  = 0;
            for(auto e : pq[T])
            {
                if(P.count(e.second)) continue;
                else 
                {
                    cout << e.first << "\n";
                    b = 1;
                    break;
                    // break;
                }
            }

            if(!b)
            cout << "0\n";
        }
    }
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 86