Submission #959483

#	Time	Username	Problem	Language	Result	Execution time	Memory
959483		irmuun	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1545 ms	268736 KiB

bitaro

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,m,q;
    cin>>n>>m>>q;
    int s[m],e[m];
    vector<int>left[n+5],right[n+5];
    for(int i=0;i<m;i++){
        cin>>s[i]>>e[i];
        right[s[i]].pb(e[i]);
        left[e[i]].pb(s[i]);
    }
    const int B=320;
    int at[n+5][B];
    int dist[n+5][B];
    memset(at,-1,sizeof at);
    memset(dist,-1,sizeof dist);
    int last[n+5],a[B],b[B];
    vector<int>used(n+5,0);
    for(int i=1;i<=n;i++){
        priority_queue<pair<int,int>>pq;
        int sz=left[i].size();
        int pos[sz];
        fill(pos,pos+sz,0);
        for(int j=0;j<sz;j++){
            pq.push({dist[left[i][j]][0]+1,j});
        }
        for(int k=0;k<B;k++){
            bool ok=false;
            while(!pq.empty()){
                int d=pq.top().ff;
                int j=pq.top().ss;
                int v=left[i][j];
                pq.pop();
                if(used[at[v][pos[j]]]==false){
                    used[at[v][pos[j]]]=true;
                    ok=true;
                    dist[i][k]=d;
                    at[i][k]=at[v][pos[j]];
                    pos[j]++;
                    if(pos[j]<B){
                        if(at[v][pos[j]]>-1){
                            pq.push({dist[v][pos[j]]+1,j});
                        }
                    }
                    break;
                }
                else{
                    pos[j]++;
                    if(pos[j]<B){
                        if(at[v][pos[j]]>-1){
                            pq.push({dist[v][pos[j]]+1,j});
                        }
                    }
                }
            }
            if(ok){
                continue;
            }
            else{
                at[i][k]=i;
                dist[i][k]=0;
                break;
            }
        }
        for(int k=0;k<B;k++){
            if(at[i][k]==-1) break;
            used[at[i][k]]=false;
        }
    }
    vector<int>dp(n+5,-1);
    for(int i=0;i<q;i++){
        int t,y;
        cin>>t>>y;
        int c[y];
        for(ll j=0;j<y;j++){
            cin>>c[j];
            used[c[j]]=true;
        }
        if(y<B){
            bool found=false;
            for(int k=0;k<B;k++){
                if(at[t][k]==-1||used[at[t][k]]==true) continue;
                cout<<dist[t][k]<<"\n";
                found=true;
                break;
            }
            if(!found){
                cout<<-1<<"\n";
            }
        }
        else{//at most sqrt(N) times
            int ans=-1;
            fill(all(dp),-1);
            dp[t]=0;
            for(int j=t;j>=1;j--){
                if(dp[j]>-1){
                    for(auto x:left[j]){
                        dp[x]=max(dp[x],dp[j]+1);
                    }
                }
            }
            for(int j=1;j<=n;j++){
                if(dp[j]>-1&&used[j]==false){
                    ans=max(ans,dp[j]);
                }
            }
            for(int j=0;j<y;j++){
                used[c[j]]=false;
            }
            cout<<ans<<'\n';
        }
        for(int j=0;j<y;j++){
            used[c[j]]=false;
        }
    }
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:28:9: warning: unused variable 'last' [-Wunused-variable]
   28 |     int last[n+5],a[B],b[B];
      |         ^~~~
bitaro.cpp:28:19: warning: unused variable 'a' [-Wunused-variable]
   28 |     int last[n+5],a[B],b[B];
      |                   ^
bitaro.cpp:28:24: warning: unused variable 'b' [-Wunused-variable]
   28 |     int last[n+5],a[B],b[B];
      |                        ^

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