제출 #1274395

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1274395		der_kleineprinz	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	731 ms	278648 KiB

bitaro

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 7;
const int S = 100;
int x[N],block[N],from[N],n,m,q,dp[N];
vector<pair<int,int>> path[N];
vector<int> g[N];
void prep()
{
    for(int i = 1; i <= n; i++)
    {
        path[i].push_back({0,i});
        vector<int> node;
        for(int j : g[i])
        {
            for(auto [len,o] : path[j])
            {
                if(from[o] == -1)
                {
                    node.push_back(o);
                    from[o] = len+1;
                }
                else {
                    from[o] = max(from[o],len + 1);
                }
            }
        }
        for(int id : node) path[i].push_back({from[id],id});
        sort(path[i].begin(),path[i].end(),greater<pair<int,int>>());
        while(path[i].size() > S) path[i].pop_back();
        for(int id : node) from[id] = -1;
    }
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i++) from[i] = -1;
    for(int i = 1; i <= m; i++)
    {
        int u,v;
        cin >> u >> v;
        g[v].push_back(u);
    }
    prep();
    while(q--)
    {
        int t,y;
        cin >> t >> y;
        for(int i = 1; i <= y; i++)
        {
            cin >> x[i];
            block[x[i]] = 1;
        }
        int ans = -1;
        if(y >= S)
        {
            for(int i = 1; i <= n; i++) dp[i] = -1;
            dp[t] = 0;
            for(int i = t; i >= 1; i--)
            {
                if(dp[i] == -1) continue;
                if(!block[i]) ans = max(ans,dp[i]);
                for(int j : g[i]) dp[j] = max(dp[j],dp[i] + 1);
            }
        }
        else
        {
            for(auto [len,o] : path[t])
            {
                if(!block[o]) ans = max(ans,len);
            }
        }
        for(int i = 1; i <= y; i++) block[x[i]] = 0;
        cout << ans <<'\n';
    }
}

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