Submission #95472

#	Time	Username	Problem	Language	Result	Execution time	Memory
95472		Retro3014	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1713 ms	420948 KiB

bitaro

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

using namespace std;
#define MAX_N 100000


int N, M, Q;
int Y, SQ;
vector<int> gp[MAX_N+1];
vector<pair<int, int> > edge;
struct S{
	S (int idx, int data) : idx(idx), data(data) {}
	int idx, data;
	bool operator <(const S &a)const{
		if(data==a.data){
			return idx<a.idx;
		}
		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;
	}
}

priority_queue<S> pq;
vector<S> tmpv;

void solve(){
	SQ = sqrt(Y);
	for(int i=1; i<=N; i++){
		vt[i].push_back({i, 0});
	}
	for(int i=0; i<edge.size(); i++){
		pair<int, int> p = edge[i];
		while(!tmpv.empty())	tmpv.pop_back();
		for(int j=0; j<vt[p.second].size(); j++){
			tmpv.push_back(vt[p.second][j]);
		}
		while(!vt[p.second].empty())	vt[p.second].pop_back();
		int idx1 = 0, idx2 = 0;
		while((idx1<vt[p.first].size() || idx2<tmpv.size()) && vt[p.second].size()<SQ){
			if(idx1==vt[p.first].size()){
				if(!chk[tmpv[idx2].idx]){
					vt[p.second].push_back(tmpv[idx2]);
					chk[tmpv[idx2].idx] = true;
				}
				idx2++;
			}else if(idx2==tmpv.size()){
				if(!chk[vt[p.first][idx1].idx]){
					vt[p.second].push_back({vt[p.first][idx1].idx, vt[p.first][idx1].data+1});
					chk[vt[p.first][idx1].idx] = true;
				}
				idx1++;
			}else{
				if(vt[p.first][idx1].data+1>=tmpv[idx2].data){
					if(!chk[vt[p.first][idx1].idx]){
						vt[p.second].push_back({vt[p.first][idx1].idx, vt[p.first][idx1].data+1});
						chk[vt[p.first][idx1].idx] = true;
					}
					idx1++;
				}else{
					if(!chk[tmpv[idx2].idx]){
						vt[p.second].push_back(tmpv[idx2]);
						chk[tmpv[idx2].idx] = true;
					}
					idx2++;
				}
			}
		}
		for(int j=0; j<vt[p.second].size(); j++){
			chk[vt[p.second][j].idx] = 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);
		edge.push_back(make_pair(a, b));
	}
	sort(edge.begin(), edge.end());
	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:50:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0; j<gp[i].size(); j++){
                 ~^~~~~~~~~~~~~
bitaro.cpp:58:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(idx<vt[now.t].size()){
         ~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:62: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:78:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<edge.size(); i++){
               ~^~~~~~~~~~~~
bitaro.cpp:81:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<vt[p.second].size(); j++){
                ~^~~~~~~~~~~~~~~~~~~~
bitaro.cpp:86:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while((idx1<vt[p.first].size() || idx2<tmpv.size()) && vt[p.second].size()<SQ){
          ~~~~^~~~~~~~~~~~~~~~~~~
bitaro.cpp:86:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while((idx1<vt[p.first].size() || idx2<tmpv.size()) && vt[p.second].size()<SQ){
                                     ~~~~^~~~~~~~~~~~
bitaro.cpp:86:77: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while((idx1<vt[p.first].size() || idx2<tmpv.size()) && vt[p.second].size()<SQ){
                                                          ~~~~~~~~~~~~~~~~~~~^~~
bitaro.cpp:87:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(idx1==vt[p.first].size()){
       ~~~~^~~~~~~~~~~~~~~~~~~~
bitaro.cpp:93:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    }else if(idx2==tmpv.size()){
             ~~~~^~~~~~~~~~~~~
bitaro.cpp:115:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<vt[p.second].size(); j++){
                ~^~~~~~~~~~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:143:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<Query.size(); i++){
               ~^~~~~~~~~~~~~
bitaro.cpp:122: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:125: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:132: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:137: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: 7 / 7
• Subtask 3: 86 / 86