Submission #1223098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223098		poat	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	2083 ms	395404 KiB

bitaro

#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 = 50, inf = 0, mod = 1e9 + 7;
const double eps = 1e-6;

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

int D[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;

        vector<int> vec(y);
        for(auto &i : vec)
        {
            cin >> i;
            D[i] = -1e9;
        }

        if(y < K)
        {
            int mx = -1;
            for(auto i : S[x])
            {
                if(D[i.second] >= 0)
                    mx = i.first;
            }

            cout << mx << "\n";
        }
        else   
        {
            for(int i = 1; i <= n; i++)
            {
                for(auto j : gr[i])
                    D[j] = max(D[j], D[i] + 1);
            }

            cout << max(-1, D[x]) << '\n';

            for(int i = 1; i <= n; i++)
                D[i] = 0;
        }

        for(auto i : vec)
            D[i] = 0;
    }
}

signed main()
{   
    // txt;
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T = 1;
    for(; T--; solve());
}
/*
*/

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