Submission #553486

#	Time	Username	Problem	Language	Result	Execution time	Memory
553486		MohamedAhmed04	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1194 ms	259524 KiB

bitaro

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 1e5 + 10 ;
const int SQRT = 317 ;

int arr[MAX] ;
int n , m , q ;

vector< vector<int> >adj(MAX) ;
int vis[MAX] ;

array< pair<int , int> , SQRT>dp[MAX] ;

vector<int>topo ;

int mark[MAX] ;
int id = 0 ;

array< pair<int , int> , SQRT>Merge(array< pair<int , int> , SQRT>&a , array< pair<int , int> , SQRT>&b)
{
	++id ;
	array< pair<int , int> , SQRT>res ;
	int i = 0 , j = 0 ;
	for(int k = 0 ; k < SQRT ; ++k)
	{
		while(i < SQRT && a[i].second != -1 && mark[a[i].second] == id)
			++i ;
		while(b[j].second != -1 && mark[b[j].second] == id)
			++j ;
		if(a[i].first >= b[j].first)
			res[k] = a[i] , ++i ;
		else
			res[k] = b[j] , ++j ;
		if(res[k].second != -1)
			mark[res[k].second] = id ;
	}
	return res ;
}

void dfs(int node)
{
	vis[node] = 1 ;
	for(int i = 0 ; i < SQRT ; ++i)
		dp[node][i] = {-1e9 , -1} ;
	dp[node][0] = {0 , node} ;
	for(auto &child : adj[node])
	{
		if(!vis[child])
			dfs(child) ;
		array< pair<int , int> , SQRT>b = dp[child] ;
		for(int i = 0 ; i < SQRT ; ++i)
			b[i].first++ ;
		dp[node] = Merge(dp[node] , b) ;
	}
	topo.push_back(node) ;
}

int SolveSmall(int node)
{
	int ans = -1 ;
	for(int i = 0 ; i < SQRT ; ++i)
	{
		if(dp[node][i].second == -1)
			break ;
		if(mark[dp[node][i].second] != id)
		{
			ans = dp[node][i].first ;
			break ;					
		}
	}
	return ans ;
}

int dp2[MAX] ;

int SolveBig(int x)
{
	for(int i = 1 ; i <= n ; ++i)
		dp2[i] = -1e9 ;
	dp2[x] = 0 ;
	int ans = -1 ;
	for(auto &node : topo)
	{
		for(auto &child : adj[node])
			dp2[child] = max(dp2[child] , dp2[node] + 1) ;
		if(mark[node] != id)
			ans = max(ans , dp2[node]) ;
	}
	return ans ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>m>>q ;
	for(int i = 0 ; i < m ; ++i)
	{
		int x , y ;
		cin>>x>>y ;
		adj[y].push_back(x) ;
	}
	for(int i = 1 ; i <= n ; ++i)
	{
		if(vis[i])
			continue ;
		dfs(i) ;
	}
	reverse(topo.begin() , topo.end()) ;
	while(q--)
	{
		++id ;
		int node , sz ;
		cin>>node>>sz ;
		for(int i = 0 ; i < sz ; ++i)
		{
			int x ;
			cin>>x ;
			mark[x] = id ;			
		}
		if(sz < SQRT)
			cout<<SolveSmall(node)<<"\n" ;
		else
			cout<<SolveBig(node)<<"\n" ;
	}
	return 0 ;
}		

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