Submission #346731

#	Time	Username	Problem	Language	Result	Execution time	Memory
346731		CaroLinda	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1816 ms	425488 KiB

bitaro

#include <bits/stdc++.h>

#define ll long long
#define sz(x) x.size()
#define all(x) x.begin(),x.end()

const int MAXN = 1e5+10 ;
const int MAGIC = 317 ;

using namespace std ;

int N , M , Q ;
int T[MAXN] ;
vector<int> adj[MAXN] ;
vector<int> occupied[MAXN] ;
int ansQuery[MAXN] ;
vector< pair<int,int> > farFromMe[MAXN] ;
bool freq[MAXN] ;
vector<int> lightQueries[MAXN] , heavyQueries[MAXN] ;
int dp[MAXN] ;

int main()
{
	scanf("%d %d %d", &N, &M, &Q ) ;
	for(int i = 1 , u ,v ; i <= M ; i++ )
	{
		scanf("%d %d", &u, &v ) ;
		if( u < v ) swap(u,v) ;
		adj[u].push_back(v) ;
	}	

	for(int i = 1 ,t , y, x ; i <= Q ; i++ )
	{
		scanf("%d %d", &t , &y ) ;		
		for(int j = 0 ; j < y ; j++ )
		{
			scanf("%d", &x ) ;
			occupied[i].push_back(x) ;
		}
		
		if( y < MAGIC ) lightQueries[ t ].push_back(i) ;
		else heavyQueries[t].push_back(i) ;

		ansQuery[i] = -1 ;
	}
	
	for(int i = 1 ; i <= N ; i++ )
	{
		
		for(auto e : adj[i] )
		{
			int idxMe = 0 , idxThem = 0 ;

			vector<pair<int,int> > aux ;

			while( (idxMe < sz(farFromMe[i]) || idxThem < sz(farFromMe[e] ) ) && sz(aux) < MAGIC )
			{
				if( idxThem < sz(farFromMe[e] ) && freq[ farFromMe[e][idxThem].second ] )
				{
					idxThem++ ;
					continue ;
				}
				if( idxMe < sz(farFromMe[i] ) && freq[ farFromMe[i][idxMe].second ] )
				{
					idxMe++ ;
					continue ;
				}

				if( idxMe == sz(farFromMe[i] ) || (idxThem < sz(farFromMe[e] ) && farFromMe[e][idxThem].first+1 >= farFromMe[i][idxMe].first ) ) 
				{
					aux.push_back( make_pair(farFromMe[e][idxThem].first+1, farFromMe[e][idxThem].second ) ) ; 
					idxThem++ ;
				}
				else 
				{
					aux.push_back( farFromMe[i][idxMe] ) ;
					idxMe++ ;
				}

				freq[ aux.back().second ] = true ;

			}

			for(auto e : aux ) freq[e.second ] = false ;
			swap(farFromMe[i], aux) ;

		}

		if( sz(farFromMe[i] ) < MAGIC ) farFromMe[i].push_back( make_pair(0, i) ) ;

		for(auto party : lightQueries[i] )
		{
			for(auto e : occupied[party] ) freq[e] = true ;

			for(int j = 0 ; j < sz(farFromMe[i] ) ; j++ )		
			{
				if( freq[ farFromMe[i][j].second ] ) continue ;
				ansQuery[ party ] = farFromMe[i][j].first ;
				break ;
			}

			for(auto e : occupied[ party ] ) freq[e] = false ;

		}

	}

/*	for(int i= 1 ; i <= N ; i++ )
	{
		cout << i << endl ;
		for(auto e : farFromMe[i] ) cout << e.first << " " << e.second << endl ;
		cout << endl ;
	}  */

	for(int i = 1 ; i <= N ; i++ )
		for(auto party : heavyQueries[i] )
		{

			for(auto e : occupied[party] ) freq[e] = true ;

			for(int j = 1 ; j <= i ; j++ )
			{
				dp[j] = freq[j] ? -1 : 0 ;

				for(auto e : adj[j] )
					if( dp[e] != -1 ) dp[j] = max(dp[j], dp[e]+1 ) ;
					
			}

			for(auto e : occupied[party] ) freq[e] = false ;					

			ansQuery[party] = dp[i] ;

		}

	for(int i = 1 ; i <= Q ; i++ ) printf("%d\n", ansQuery[i] ) ;

}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:56:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |    while( (idxMe < sz(farFromMe[i]) || idxThem < sz(farFromMe[e] ) ) && sz(aux) < MAGIC )
      |                  ^
bitaro.cpp:56:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |    while( (idxMe < sz(farFromMe[i]) || idxThem < sz(farFromMe[e] ) ) && sz(aux) < MAGIC )
      |                                                ^
bitaro.cpp:58:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     if( idxThem < sz(farFromMe[e] ) && freq[ farFromMe[e][idxThem].second ] )
      |                 ^
bitaro.cpp:63:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     if( idxMe < sz(farFromMe[i] ) && freq[ farFromMe[i][idxMe].second ] )
      |               ^
bitaro.cpp:69:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     if( idxMe == sz(farFromMe[i] ) || (idxThem < sz(farFromMe[e] ) && farFromMe[e][idxThem].first+1 >= farFromMe[i][idxMe].first ) )
      |               ^
bitaro.cpp:69:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     if( idxMe == sz(farFromMe[i] ) || (idxThem < sz(farFromMe[e] ) && farFromMe[e][idxThem].first+1 >= farFromMe[i][idxMe].first ) )
      |                                                ^
bitaro.cpp:95:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |    for(int j = 0 ; j < sz(farFromMe[i] ) ; j++ )
      |                      ^
bitaro.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |  scanf("%d %d %d", &N, &M, &Q ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:27:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |   scanf("%d %d", &u, &v ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~
bitaro.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |   scanf("%d %d", &t , &y ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
bitaro.cpp:37:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |    scanf("%d", &x ) ;
      |    ~~~~~^~~~~~~~~~~

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