제출 #1192969

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1192969		justinlgl20	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	2099 ms	225988 KiB

bitaro

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

#define all(x) (x).begin(), (x).end()

ostream& operator<<(ostream& os,pair<int,int>v){
	os<<"("<<v.first<<" "<<v.second<<")";return os;
}
template<template<typename> class Container, typename T>
ostream& operator<<(ostream& os,Container<T> v){
	int s=v.size();os<<"{";for(auto i:v)os<<i<<(--s?", ":"}");return os;
}

void _print() {
	cerr<<"]\n";
}
template<typename T,typename... V>
void _print(T t, V... v){
	cerr<<t;if(sizeof...(v))cerr<<", ";_print(v...);
}
#ifdef DEBUG
#define dbg(x...)cerr<<"\e[91m"<<__func__<<":"<<__LINE__<<" "<<"["<<#x<<"] = [";_print(x);cerr<<"\e[39m"<<"\n";
#else
#define dbg(x...)
#endif
#define pii pair<int,int>
#define f first
#define s second

const int SQ = 350;

vector<int> pull[100005];
vector<pii> best[100005];

int32_t main() {
	// for each cantde, keep track of the sqrt best cantdes that can go to it
	int n,m,q;cin>>n>>m>>q;
	for(int i=0;i<m;i++){
		int u,v;cin>>u>>v;pull[v].emplace_back(u);
	}
	for(int i=1;i<=n;i++){
		best[i].emplace_back(0, i);
		gp_hash_table<int,int> b;
		for(int k:pull[i]){
			// merge best[i] with best[k] and take the sqrt best things (can't be same element)
			for(pii j:best[k]){
				b[j.s]=max(b[j.s],j.f+1);
			}
		}
		for(pii j:b){
			best[i].emplace_back(j.s,j.f);
		}
		sort(all(best[i]));reverse(all(best[i]));best[i].resize(min((int)best[i].size(),SQ));
		dbg(i,best[i]);
	}
	dbg("DONE");
	while(q--){
		int dest,y;cin>>dest>>y;vector<int> cant(y);for(int i=0;i<y;i++)cin>>cant[i];
		dbg(dest,cant);
		gp_hash_table<int,int> bad;
		for(int i:cant)bad[i]=1;
		if(y>=SQ){
			dbg("BEEG");
			vector<int> best(n+4,0);
			for(int i:cant)best[i]=-1e9;
			for(int i=1;i<=n;i++){
				for(int j:pull[i]){
					best[i]=max(best[i],best[j]+1);
				}
				dbg(i,best[i]);
			}
			if(best[dest]<0){
				cout<<"-1\n";
			}else{
				cout<<best[dest]<<"\n";
			}
		}else{
			bool done=0;
			for(int i=0;i<best[dest].size();i++){
				if(!bad[best[dest][i].s]){
					done=1;
					cout<<best[dest][i].f<<"\n";
					break;
				}
			}
			if(!done){
				cout<<"-1\n";
			}
		}
	}
}

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