Submission #114846

#	Time	Username	Problem	Language	Result	Execution time	Memory
114846		shayan_p	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1711 ms	272212 KiB

bitaro

// High above the clouds there is a rainbow...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=1e5+10,SQ=320;

pii dp[maxn][SQ];
int SZ[maxn],arr[maxn],DP[maxn];

vector<int>tpl,v[maxn],g[maxn];

bool mark[maxn];

void dfs(int u){
    mark[u]=1;
    for(int y:v[u]){
	if(!mark[y])
	    dfs(y);
    }
    tpl.PB(u);
}

pii memo[maxn];

void Merge(int a,int b){
    int pt=0,pt1=0,pt2=0;
    while(pt<SZ[a]+SZ[b]){
	if(pt2==SZ[b] || (pt1!=SZ[a] && dp[a][pt1].F > dp[b][pt2].F) ) memo[pt++]=dp[a][pt1++];
	else memo[pt++]=dp[b][pt2++];
    }
    SZ[a]=0;
    for(int i=0;i<pt;i++){
	if(SZ[a]==SQ) break;
	if(mark[ memo[i].S ]) continue;
	mark[memo[i].S]=1;
	dp[a][SZ[a]++]=memo[i];
    }
    for(int i=0;i<SZ[a];i++){
	mark[dp[a][i].S]=0;
    }
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    
    int n,m,q;cin>>n>>m>>q;
    
    for(int i=0;i<m;i++){
	int a,b;cin>>a>>b; --a,--b;
	v[a].PB(b);
	g[b].PB(a);
    }
    for(int i=0;i<n;i++){
	if(!mark[i])
	    dfs(i);
    }

    reverse(tpl.begin(),tpl.end());

    memset(mark,0,sizeof mark);
    
    for(int i:tpl){
	for(int j:g[i]){
	    Merge(i,j);
	}
	for(int j=0;j<SZ[i];j++){
	    dp[i][j].F++;
	}
	if(SZ[i]<SQ){
	    dp[i][SZ[i]++]={0,i};
	}
    }
    
    while(q--){
	int u,c,ans=-1; cin>>u>>c; --u;
	for(int i=0;i<c;i++){
	    cin>>arr[i];
	    mark[--arr[i]]=1;
	}

	if(c>=SQ){
	    for(int i:tpl){
		DP[i]= mark[i] ? -1 : 0;
		for(int j:g[i]){
		    if(DP[j]!=-1)
			DP[i]= max(DP[i], DP[j]+1);
		}
	    }
	    ans= DP[u];
	}
	else{
	    for(int i=0;i<SZ[u];i++){
		if(!mark[dp[u][i].S]){
		    ans=dp[u][i].F;
		    break;
		}
	    }
	}
	
	for(int i=0;i<c;i++){
	    mark[arr[i]]=0;
	}

	cout<<ans<<"\n";
    }
    return 0;
}

// Deathly mistakes:
//  * Read the problem curfully.
//  * Check maxn.
//  * Overflows.

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