Submission #1160713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160713		AHOKA	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1278 ms	125472 KiB

bitaro

#include <bits/stdc++.h>

#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

using namespace std;
 
#define threesum cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false)
#define all(a) a.begin(), a.end()
#define F first
#define S second
//#define int long long
#define pii pair<int, int>
#define ppp pair<int, pii>
#define dout cout << fixed << setprecision(15)
#define mid ((l + r) / 2)
#define lc (2 * id)
#define rc (lc + 1)

const int maxn = 1e5 + 10, maxm = 5e3 + 10, oo = 1e8 + 10, lg = 23, sq = 45, mod = 998244353;

int n, m, q, dp[maxn];

vector<int> in[maxn], out[maxn];

vector<int> del;

vector<pii> candy[maxn];

bool seen[maxn];

int small(int r){
    for(auto v : del)
        seen[v] = 1;

    int res = -1;
    for(auto [len, v] : candy[r])
        if(!seen[v])
            res = max(res, len);

    for(auto v : del)
        seen[v] = 0;

    return res;
}

int big(int r){
    for (int i = 1; i <= n;i++)
        dp[i] = 0;

    for(auto i : del)
        dp[i] = -oo;

    for (int v = 1; v <= r;v++)
        for(auto u : in[v])
            dp[v] = max(dp[v], dp[u] + 1);

    return (dp[r] < 0 ? -1 : dp[r]);
}

signed main()
{
    threesum;
    cin >> n >> m >> q;
    for (int i = 1; i <= m;i++){
        int u, v;
        cin >> u >> v;
        
        out[u].push_back(v);
        in[v].push_back(u);
    }

    for (int v = 1; v <= n;v++)
        candy[v].push_back({0, v});

    for (int v = 1; v <= n;v++){
        sort(all(candy[v]));
        reverse(all(candy[v]));

        vector<pii> vec;

        for(auto [len, u] : candy[v]){
            if(vec.size() >= sq)
                break;

            if(seen[u])
                continue;

            vec.push_back({len, u});
            seen[u] = 1;
        }

        candy[v] = vec;

        for(auto [len, u] : candy[v])
            seen[u] = 0;

        for(auto u : out[v])
            for(auto [len, w] : candy[v])
                candy[u].push_back({len + 1, w});
    }

    while (q--)
    {
        int v, k;
        cin >> v >> k;
        for (int i = 1; i <= k; i++)
        {
            int x;
            cin >> x;
            del.push_back(x);
        }

        if (k + 5 < sq)
            cout << small(v) << "\n";
        else
            cout << big(v) << "\n";

        del.clear();
    }
}

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