Submission #1224829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224829		salmon	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1022 ms	401600 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;

int N,M,Q;
vector<int> children[100100];
int taken[100100];
int u,v;
vector<pair<int,int>> guys[100100];
const int B = 500;
int visited[100100];
int memo[100100];

int main(){
	
	scanf(" %d",&N);
	scanf(" %d",&M);
	scanf(" %d",&Q);
	
	for(int i = 0; i < M; i++){
		scanf(" %d",&u);
		scanf(" %d",&v);
		
		if(u > v) swap(u,v);
		
		children[v].push_back(u);
	}
	
	
	for(int i = 0; i <= N; i++){
		taken[i] = 0;
	}
	
	for(int i = 1; i <= N; i++){
		guys[i] = {make_pair(0,i)};
		
		for(int j : children[i]){
			vector<pair<int,int>> v;
			
			int it = 0;
			int it1 = 0;
			
			for(int k = 0; k < B && (it != guys[i].size() || it1 != guys[j].size()); k++){
				if(it == guys[i].size()){
					v.push_back(guys[j][it1]);
					v.back().first++;
					taken[guys[j][it1].second] = i;
					it1++;
				}
				else if(it1 == guys[j].size()){
					v.push_back(guys[i][it]);
					taken[guys[i][it].second] = i;
					it++;
				}
				else{
					if(guys[i][it].first > guys[j][it1].first){
						v.push_back(guys[i][it]);
						taken[guys[i][it].second] = i;
						it++;
					}
					else{
						v.push_back(guys[j][it1]);
						v.back().first++;
						taken[guys[j][it1].second] = i;
						it1++;
					}
				}
				
				while(it != guys[i].size() && taken[guys[i][it].second] == i) it++;
				while(it1 != guys[j].size() && taken[guys[j][it1].second] == i) it1++;
			}

			guys[i] = v;
			
			for(pair<int,int> ii : guys[i]) taken[ii.second] = 0;
		}
		
		//for(pair<int,int> ii : guys[i]) printf("%d %d\n",ii.first,ii.second);
		//printf("\n");
	}
	
	for(int i = 0; i <= N; i++) visited[i] = -1;
	
	for(int i = 0; i < Q; i++){
		int h,K;
		scanf(" %d",&h);
		scanf(" %d",&K);
		//printf("f %d %d\n",h,K);
		for(int k = 0; k < K; k++){
			int h1;
			scanf(" %d",&h1);
			
			visited[h1] = i;
		}
		
		if(K < B){		
			int best = -1;
			
			for(int j = 0; j < guys[h].size(); j++){
				if(visited[guys[h][j].second] != i){
					best = guys[h][j].first;
					//printf("%d %d\n",guys[h][j].first,guys[h][j].second);
					break;
				}
			}
			
			printf("%d\n",best);
		}
		else{
			
			for(int i = 0; i <= h; i++) memo[i] = -N - 2;
			
			memo[h] = 0;
			
			for(int i = h; i >= 1; i--){
				for(int j : children[i]) memo[j] = max(memo[j], memo[i] + 1);
			}
			
			int best = -1;
			
			for(int j = 0; j <= h; j++) if(visited[j] != i) best = max(best, memo[j]);
			
			printf("%d\n",best);
		}
	}
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
bitaro.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         scanf(" %d",&M);
      |         ~~~~~^~~~~~~~~~
bitaro.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         scanf(" %d",&Q);
      |         ~~~~~^~~~~~~~~~
bitaro.cpp:20:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |                 scanf(" %d",&u);
      |                 ~~~~~^~~~~~~~~~
bitaro.cpp:21:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |                 scanf(" %d",&v);
      |                 ~~~~~^~~~~~~~~~
bitaro.cpp:85:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |                 scanf(" %d",&h);
      |                 ~~~~~^~~~~~~~~~
bitaro.cpp:86:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |                 scanf(" %d",&K);
      |                 ~~~~~^~~~~~~~~~
bitaro.cpp:90:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |                         scanf(" %d",&h1);
      |                         ~~~~~^~~~~~~~~~~

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