Submission #1229528

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

bitaro

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

#define ll int
#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<vector<pair<ll,ll>>> pq;

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

    adj.resize(N);
    pq.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 = 100;
    //precompute
    vector<ll> vis(N, -1);
    vector<ll> sz(N, 0);

    for(ll i = 0; i < N; i++)
    {
        pq[i].emplace_back(0, i);
        sz[i]++;
        
        sort(all(pq[i]), greater<pair<ll,ll>>());
        ll ij = 0; // last free
        for(ll k = 0; k < sz[i] && ij <= SQRT+5; k++)
        {
            if(vis[pq[i][k].second] != i)
            {
                vis[pq[i][k].second] = i;
                pq[i][ij] = pq[i][k];
                ij++;
            }
        }
        sz[i] = ij;
        pq[i].resize(sz[i]);

        for(auto e : adj[i])
        {
            for(ll k = 0; k < sz[i]; k++)
            {   
                auto [d,v] = pq[i][k]; 
                pq[e].emplace_back(d+1, v);
                sz[e]++;
            }
        }

    }
    
    int ij = 0; 
    vector<ll> del(N, -1);
    while(Q--)
    {
        ll T, Y;
        cin >> T >> Y;
        --T;
        ll x;
        for(ll i = 0; i < Y; i++)
        {
            cin >> x;
            del[--x] = ij;
        }

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

            cout << dp[T] << "\n";
        }
        else
        {
            // continue;
            bool b  = 0;
            for(ll k = 0; k < sz[T]; k++)
            {
                auto e = pq[T][k];
                // cout << e.first << " " << e.second << " " << del[e.second] << " " << ij << "\n";
                if(del[e.second] == ij) continue;
                else 
                {
                    cout << e.first << "\n";
                    b = 1;
                    break;
                    // break;
                }
            }

            if(!b)
                cout << "-1\n";
        }
        ij++;
    }
}

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