제출 #1286723

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

bitaro

#include <bits/stdc++.h>
using namespace std;
const long long mxN = 1e5+5;
const long long INF = 1e16;
const long long MOD = 1e9+7;
const long long SQRT = 100;
vector<long long> radj[mxN];
vector<pair<long long, long long>> paths[mxN];
#define endl '\n'
void solve(){
    long long n,m,k;
    cin >> n >> m >> k;
    for(int i=0; i<m; i++){
        long long a,b;
        cin >> a >> b;
        radj[b].push_back(a);
    }
    vector<long long> from(n+1,-1);
    for(int i=1; i<=n; i++){
        paths[i].push_back({0,i});
        vector<long long> have;
        for(auto prev : radj[i]){
            for(auto p : paths[prev]){
                if(from[p.second]==-1){
                    have.push_back(p.second);
                    from[p.second]=p.first+1;
                }
                else{
                    from[p.second]=max(from[p.second],p.first+1);
                }
            }
        }
        for(auto x : have){
            paths[i].push_back({from[x],x});
        }
        sort(paths[i].rbegin(),paths[i].rend());
        while(paths[i].size()>SQRT){
            paths[i].pop_back();
        }
        for(auto x : have){
            from[x]=-1;
        }
    }
    vector<bool> blocked(n+1);
    for(int i=0; i<k; i++){
        long long t,y;
        cin >> t >> y;
        vector<long long> c(y);
        for(int j=0; j<y; j++){
            cin >> c[j];
            blocked[c[j]]=true;
        }
        long long ans = -1;
        if(y>=SQRT){
            vector<long long> dp(t+1,-1);
            dp[t]=0;
            for(int i=t; i>=1; i--){
                if(dp[i]==-1){
                    continue;
                }
                if(!blocked[i]){
                    ans=max(ans,dp[i]);
                }
                for(auto prev : radj[i]){
                    dp[prev]=max(dp[prev],dp[i]+1);
                }
            }
        }
        else{
            for(auto [dist,idx] : paths[t]){
                if(!blocked[idx]){
                    ans = dist;
                    break;
                }
            }
        }
        cout << ans << endl;
        for(auto x : c){
            blocked[x]=false;
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long t = 1; //cin >> t;
    while(t--){
        solve();
    }
}

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