Submission #285086

#	Time	Username	Problem	Language	Result	Execution time	Memory
285086		Plurm	Bitaro’s Party (JOI18_bitaro)	C++11	14 / 100	1533 ms	147476 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
const int THRESH = 160;
vector<int> ord;
vector<int> g[100005];
vector<int> rg[100005];
bool found[100005];
void dfs(int u){
	if(found[u]) return;
	found[u] = true;
	for(int v : g[u]){
		dfs(v);
	}
	ord.push_back(u);
}
vector<pair<int,int> > dp[100005]; // | dp[i] | <= THRESH.
void merge(vector<pair<int,int> >& dest, vector<pair<int,int> > src){
	for(auto& v : src) v.first++;
	vector<pair<int,int> > newVec;
	int ptr1 = 0;
	int ptr2 = 0;
	while(ptr1 < dest.size() && ptr2 < src.size() && newVec.size() < THRESH){
		if(dest[ptr1] > src[ptr2]){
			if(newVec.empty() || newVec.back().second != dest[ptr1].second) newVec.emplace_back(dest[ptr1]);
			ptr1++;
		}else{
			if(newVec.empty() || newVec.back().second != src[ptr2].second) newVec.emplace_back(src[ptr2]);
			ptr2++;
		}
	}
	while(newVec.size() < THRESH && ptr1 < dest.size()){
		if(newVec.empty() || newVec.back().second != dest[ptr1].second) newVec.emplace_back(dest[ptr1]);
		ptr1++;
	}
	while(newVec.size() < THRESH && ptr2 < src.size()){
		if(newVec.empty() || newVec.back().second != src[ptr2].second) newVec.emplace_back(src[ptr2]);
		ptr2++;
	}
	dest = newVec;
}
bool isBusy[100005];
int subdp[100005];
int recalculateAnswer(int t){
	for(int u : ord){
		subdp[u] = isBusy[u] ? -10000000 : 0;
		for(int v : rg[u]){
			subdp[u] = max(subdp[u], subdp[v]+1);
		}
	}
	return subdp[t] < 0 ? -1 : subdp[t];
}
int main(){
	int n, m, q;
	scanf("%d%d%d",&n,&m,&q);
	for(int i = 0; i < m; i++){
		int s,e;
		scanf("%d%d",&s,&e);
		g[s].push_back(e);
		rg[e].push_back(s);
	}
	for(int i = 1; i <= n; i++) dfs(i);
	reverse(ord.begin(), ord.end());
	for(int u : ord){
		for(int v : rg[u]){
			merge(dp[u], dp[v]);
		}
		merge(dp[u], {make_pair(-1, u)});
		/*
		printf("DBG [%d]\n", u);
		for(auto v : dp[u]){
			printf("%d %d\n", v.first, v.second);
		}
		*/
	}
	int t, y;
	for(int qq = 0; qq < q; qq++){
		scanf("%d%d",&t,&y);
		vector<int> busy;
		busy.reserve(y);
		for(int i = 0; i < y; i++){
			int c;
			scanf("%d",&c);
			busy.push_back(c);
			isBusy[c] = true;
		}
		int ans = -1;
		if(y < THRESH-1){
			for(auto p : dp[t]){
				if(isBusy[p.second]) continue;
				ans = p.first;
				break;
			}
		}else{
			ans = recalculateAnswer(t);
		}
		for(int c : busy) isBusy[c] = false;
		printf("%d\n",ans);
	}
	return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'void merge(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >)':
bitaro.cpp:22:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  while(ptr1 < dest.size() && ptr2 < src.size() && newVec.size() < THRESH){
      |        ~~~~~^~~~~~~~~~~~~
bitaro.cpp:22:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  while(ptr1 < dest.size() && ptr2 < src.size() && newVec.size() < THRESH){
      |                              ~~~~~^~~~~~~~~~~~
bitaro.cpp:31:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  while(newVec.size() < THRESH && ptr1 < dest.size()){
      |                                  ~~~~~^~~~~~~~~~~~~
bitaro.cpp:35:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  while(newVec.size() < THRESH && ptr2 < src.size()){
      |                                  ~~~~~^~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |  scanf("%d%d%d",&n,&m,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
bitaro.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |   scanf("%d%d",&s,&e);
      |   ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   77 |   scanf("%d%d",&t,&y);
      |   ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:82:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   82 |    scanf("%d",&c);
      |    ~~~~~^~~~~~~~~

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