Submission #95468

#	Time	Username	Problem	Language	Result	Execution time	Memory
95468		Retro3014	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2058 ms	87256 KiB

bitaro

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <vector>
#include <math.h>

using namespace std;
#define MAX_N 100000


int N, M, Q;
int Y, SQ;
vector<int> gp[MAX_N+1];
struct S{
	S (int idx, int data) : idx(idx), data(data) {}
	int idx, data;
	bool operator <(const S &a)const{
		return data>a.data;
	}
};
vector<S> vt[MAX_N+1];
struct QUERY{
	int t, y;
	vector<int> c;
};
vector<QUERY> Query;


bool chk[MAX_N+1];
int dist[MAX_N+1];

void solve_query(QUERY now){
	for(int i=0; i<now.y; i++){
		chk[now.c[i]] = true;
	}
	if(now.y>=SQ){
		int ans = -1;
		for(int i = now.t; i>=1; i--){
			if(i!=now.t && dist[i]==0){
				continue;
			}
			if(!chk[i]){
				ans = max(ans, dist[i]);
			}
			for(int j=0; j<gp[i].size(); j++){
				dist[gp[i][j]] = max(dist[gp[i][j]], dist[i]+1);
			}
			dist[i] = 0;
		}
		printf("%d\n", ans);
	}else{
		int idx = 0;
		while(idx<vt[now.t].size()){
			if(chk[vt[now.t][idx].idx])	idx++;
			else break;
		}
		if(idx==vt[now.t].size())	printf("-1\n");
		else	printf("%d\n", vt[now.t][idx].data);
	}
	for(int i=0; i<now.y; i++){
		chk[now.c[i]] = false;
	}
}


void solve(){
	SQ = sqrt(Y);
	for(int i=1; i<=N; i++){
		vt[i].push_back({i, 0});
		for(int j=0; j<gp[i].size(); j++){
			for(int k=0; k<vt[gp[i][j]].size(); k++){
				vt[i].push_back({vt[gp[i][j]][k].idx, vt[gp[i][j]][k].data+1});
			}
		}
		sort(vt[i].begin(), vt[i].end());
		int index = 0, cnt = 0;
		while(index<vt[i].size() && cnt<SQ){
			if(!chk[vt[i][index].idx]){
				cnt++;
				chk[vt[i][index].idx] = true;
			}else{
				vt[i][index].data = -1;
			}
			index++;
		}
		sort(vt[i].begin(), vt[i].end());
		while(vt[i].size()>SQ || vt[i].back().data==-1)	vt[i].pop_back();
		for(int j=0; j<vt[i].size(); j++){
			chk[vt[i][j].idx] = false;
		}
		for(int j=1; j<=N; j++){
			chk[j] = false;
		}
	}
}

int main(){
	scanf("%d%d%d", &N, &M, &Q);
	for(int i=0; i<M; i++){
		int a, b;
		scanf("%d%d", &a, &b);
		gp[b].push_back(a);
	}
	for(int i=0; i<Q; i++){
		QUERY tmp;
		scanf("%d%d", &tmp.t, &tmp.y);
		Y+=tmp.y;
		while(!tmp.c.empty())	tmp.c.pop_back();
		for(int i=0; i<tmp.y; i++){
			int x;
			scanf("%d", &x); tmp.c.push_back(x);
		}
		Query.push_back(tmp);
	}
	//cout<<1<<endl;
	solve();
	for(int i=0; i<Query.size(); i++){
		solve_query(Query[i]);
	}
	return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'void solve_query(QUERY)':
bitaro.cpp:45:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0; j<gp[i].size(); j++){
                 ~^~~~~~~~~~~~~
bitaro.cpp:53:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(idx<vt[now.t].size()){
         ~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:57:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(idx==vt[now.t].size()) printf("-1\n");
      ~~~^~~~~~~~~~~~~~~~~~
bitaro.cpp: In function 'void solve()':
bitaro.cpp:70:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<gp[i].size(); j++){
                ~^~~~~~~~~~~~~
bitaro.cpp:71:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0; k<vt[gp[i][j]].size(); k++){
                 ~^~~~~~~~~~~~~~~~~~~~
bitaro.cpp:77:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(index<vt[i].size() && cnt<SQ){
         ~~~~~^~~~~~~~~~~~~
bitaro.cpp:87:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(vt[i].size()>SQ || vt[i].back().data==-1) vt[i].pop_back();
         ~~~~~~~~~~~~^~~
bitaro.cpp:88:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<vt[i].size(); j++){
                ~^~~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:117:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<Query.size(); i++){
               ~^~~~~~~~~~~~~
bitaro.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &M, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:106:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &tmp.t, &tmp.y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:111:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &x); tmp.c.push_back(x);
    ~~~~~^~~~~~~~~~

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