Submission #367854

#	Time	Username	Problem	Language	Result	Execution time	Memory
367854		Haruto810198	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1474 ms	512432 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i,l,r,d) for(int i=(l);i<=(r);i+=(d))

#define vi vector<int>
#define pii pair<int,int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF=2147483647;
const int MOD=1000000007;
const int mod=998244353;
const double eps=1e-12;

int n,m,q;
int B;
vi edge[100001];

int dp[100001][320];
int st[100001][320];
bool valid[100001];
bool used[100001];

int dp2[100001];

void DP(int from,int to){

    int tmp_dp[320];
    int tmp_st[320];
    int cnt=0;
    int L=0, R=0;

    while(cnt<B and (L<B or R<B)){

        int D,S;

        if( R==B or ( L<B and dp[from][L]+1 > dp[to][R] ) ){
            D = dp[from][L] + 1;
            S = st[from][L];
            L++;
        }
        else{
            D = dp[to][R];
            S = st[to][R];
            R++;
        }

        if( used[S] == 0 ){
            tmp_dp[cnt] = D;
            tmp_st[cnt] = S;
            used[S] = 1;
            cnt++;
        }

    }

    FOR(i,0,cnt-1,1){
        dp[to][i] = tmp_dp[i];
        st[to][i] = tmp_st[i];
        used[ tmp_st[i] ] = 0;
    }

}

signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m>>q;

    int v1,v2;
    FOR(i,0,m-1,1){
        cin>>v1>>v2;
        v1--;
        v2--;
        edge[v1].pb(v2);
    }

    /// block size
    B = floor(sqrt(n)+eps);

    /// initialize dp
    FOR(i,0,n-1,1){
        dp[i][0] = 0;
        st[i][0] = i;
        FOR(j,1,B-1,1){
            dp[i][j] = -INF;
            st[i][j] = n;
        }
    }

    /// dp
    FOR(i,0,n-1,1){
        for(int j : edge[i]){
            //cerr<<"DP("<<i<<","<<j<<")"<<endl;
            DP(i,j);
        }
    }

    /// valid[]
    FOR(i,0,n-1,1){
        valid[i] = 1;
    }

    while(q--){

        int qidx;
        int invsz;
        vi inv;

        cin>>qidx>>invsz;
        qidx--;

        inv.clear();
        FOR(i,0,invsz-1,1){
            cin>>v1;
            v1--;
            inv.pb(v1);
            valid[v1] = 0;
        }

        if( invsz >= B ){

            //cerr<<"invsz >= B"<<endl;

            /// initialize dp2
            FOR(i,0,n-1,1){
                if( valid[i] == 0 ){
                    dp2[i] = -INF;
                }
                else{
                    dp2[i] = 0;
                }
            }

            /// dp2
            FOR(i,0,n-1,1){
                for(int j : edge[i]){
                    dp2[j] = max( dp2[j] , dp2[i]+1 );
                }
            }

            if( dp2[qidx] >= 0 ){
                cout<<dp2[qidx]<<'\n';
            }
            else{
                cout<<-1<<'\n';
            }

        }
        else{

            //cerr<<"invsz < B"<<endl;

            int ptr=0;
            while( valid[ st[qidx][ptr] ]==0 and dp[qidx][ptr]>=0 ){
                ptr++;
            }

            if( dp[qidx][ptr] >= 0 ){
                cout<<dp[qidx][ptr]<<'\n';
            }
            else{
                cout<<-1<<'\n';
            }
            /*
            FOR(i,0,B-1,1){
                cerr<<dp[qidx][i]<<" ";
            }
            cerr<<endl;
            FOR(i,0,B-1,1){
                cerr<<st[qidx][i]<<" ";
            }
            cerr<<endl;
            FOR(i,0,B-1,1){
                cerr<<valid[ st[qidx][i] ]<<" ";
            }
            cerr<<endl;
            */
        }

        for(int i : inv){
            valid[i] = 1;
        }

    }

    return 0;

}

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