제출 #1289004

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

bitaro

#include <bits/stdc++.h>
#define ll long long
#define INF 1000000
#define MAX 5000
#define mod 998244353
using namespace std;
const int bl = 50;
int main(){
    int n, m, q, a, b, t, s;
    cin>>n>>m>>q;
    vector<vector<int>> v(n + 1);
    for (int i = 1; i <= m; i++){
        cin>>a>>b;
        v[b].push_back(a);
    }
    vector<vector<vector<int>>> be(n + 1);
    vector<int> us(n + 1, 0);
    for (int i = 1; i <= n; i++){
        priority_queue<vector<int>> q;
        q.push({0, i});
        for (auto el : v[i]){
            for (auto j : be[el]){
                q.push({j[0] + 1, j[1]});
            }
        }
        int j = 0;
        while (!q.empty() && j < bl){
            int x = q.top()[1], val = q.top()[0];
            q.pop();
            if (us[x] == i) continue;
            us[x] = i;
            be[i].push_back({val, x});
            j++;
        }
    }
    vector<int> dp(n + 1, 0), blo(n + 1, -1);
    for (int i = 0; i < q; i++){
        cin>>t>>s;
        int ans = -1;
        if (s < bl){
            for (int j = 0; j < s; j++){
                cin>>a;
                blo[a] = i;
            }
            for (auto el : be[t]){
                if (blo[el[1]] != i) ans = max(ans, el[0]);
            }
        }
        else{
            dp.assign(n + 1, 0);
            for (int j = 0; j < s; j++){
                cin>>a;
                dp[a] = -INF;
            }
            for (int i = 1; i <= t; i++){
                for (auto el : v[i]){
                    dp[i] = max(dp[i], dp[el] + 1);
                }
            }
            ans = max(ans, dp[t]);
        }
        cout<<ans<<"\n";
    }
}

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