Submission #1169331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169331		DangKhoizzzz	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1257 ms	110824 KiB

bitaro

#include <bits/stdc++.h>
#define pii pair <int , int>
#define fi first
#define se second

using namespace std;

const int Block = 100;
const int maxn = 1e5 + 7;

int n , m , q , dp[maxn];
vector <int> g[maxn];
vector <pii> f[maxn];
bool checked[maxn] , ban[maxn];
int d[maxn];

void solve()
{
    cin >> n >> m >> q;
    for(int i = 1; i <= m; i++)
    {
        int u , v;
        cin >> u >> v;
        g[v].push_back(u);
    }

    for(int u = 1; u <= n; u++)
    {
        vector <pii> res;
        res.push_back({0 , u});
        for(int v: g[u])
        {
            for(pii tmp: f[v])
            {
                res.push_back({tmp.fi + 1 , tmp.se});
            }
        }

        sort(res.begin() , res.end() , greater <pii> ());

        for(pii tmp: res)
        {
            if(!checked[tmp.se] && f[u].size() < Block)
            {
                f[u].push_back(tmp);
                checked[tmp.se] = 1;
            }
        }
        for(pii tmp: res) checked[tmp.se] = 0;
    }

    while(q--)
    {
        int a , b;
        cin >> a >> b;
        for(int i = 1; i <= b; i++) 
        {
            cin >> d[i];
            ban[d[i]] = 1;
        }

        if(b < Block)
        {
            int ans = -1;
            for(pii tmp: f[a])
            {
                if(!ban[tmp.se])
                {
                    ans = max(ans , tmp.fi);
                }
            }
            cout << ans << '\n';
        }
        else
        {
            int ans = -1;
            for(int u = a; u >= 1; u--) dp[u] = -1;

            dp[a] = 0;

            for(int u = a; u >= 1; u--)
            {
                if(dp[u] != -1)
                {
                    if(!ban[u]) ans = max(ans , dp[u]);
                    for(int v: g[u])
                    {
                        dp[v] = max(dp[v] , dp[u] + 1);
                    }
                }
            }
            cout << ans << '\n';
        }

        for(int i = 1; i <= b; i++) ban[d[i]] = 0;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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