Submission #206528

#	Time	Username	Problem	Language	Result	Execution time	Memory
206528		mosiashvililuka	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	9 ms	5112 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,tes,t,i,j,zx,xc,T=300,k[100009],fx[100009],fr,sc,cnt;
int mx[100009];
bool bo[100009];
pair <int, int> dp[100009][302],tt[302];
vector <int> v[100009];
void dfsst(int q){
    bo[q]=1;
    dp[q][1].first=1;
    dp[q][1].second=q;
    for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
        if(bo[(*it)]==0) dfsst((*it));
        fr=1;sc=1;cnt=0;
        while(1){
            if(dp[q][fr].first==0&&dp[(*it)][sc].first==0) break;
            if(cnt>T) break;
            if(dp[q][fr].first>=dp[(*it)][sc].first+1){
                cnt++;tt[cnt]=dp[q][fr];fr++;
            }else{
                cnt++;tt[cnt].first=dp[(*it)][sc].first+1;tt[cnt].second=dp[(*it)][sc].second;sc++;
            }
        }
        for(j=1; j<=cnt; j++){
            dp[q][j]=tt[j];
        }
    }
}
void dfs(int q){
	bo[q]=t;
    if(fx[q]!=t) mx[q]=1;
    for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
        if(bo[(*it)]==0) dfs((*it));
        if(mx[(*it)]!=0&&mx[q]<mx[(*it)]+1) mx[q]=mx[(*it)]+1;
    }
}
int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>a>>b>>tes;
    for(i=1; i<=b; i++){
        cin>>c>>d;
        //if(c>d) swap(c,d);
        v[d].push_back(c);
    }
    for(i=1; i<=a; i++){
        if(bo[i]==1) continue;
        dfsst(i);
    }
    for(t=1; t<=tes; t++){
        cin>>c>>d;
        for(i=1; i<=d; i++){
            cin>>k[i];
            fx[k[i]]=t;
        }
        if(d>=T){
            for(i=1; i<=a; i++) mx[i]=0;
            dfs(c);
            if(mx[c]==0){
                cout<<-1<<endl;
            }else{
                cout<<mx[c]-1<<endl;
            }
        }else{
          bool zs=0;
            for(i=1; ; i++){
              if(dp[c][i].second==0) break;
                if(fx[dp[c][i].second]!=t){
                    cout<<dp[c][i].first-1<<endl;
                  zs=1;
                    break;
                }
            }
          if(zs==0) cout<<-1<<endl;
        }
    }
    return 0;
}

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