Submission #285091

#	Time	Username	Problem	Language	Result	Execution time	Memory
285091		Plurm	Bitaro’s Party (JOI18_bitaro)	C++11	Compilation error	0 ms	0 KiB

bitaro

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.
bool __used[100005];
vector<pair<int,int> > newVec;
void __append(pair<int,int> x){
	if(newVec.empty() || !__used[x.second]){
		newVec.push_back(x);
		__used[x.second] = true;
	}
}
void merge(vector<pair<int,int> >& dest, vector<pair<int,int> > src){
	for(auto& v : src) v.first++;
	int ptr1 = 0;
	int ptr2 = 0;
	while(ptr1 < dest.size() && ptr2 < src.size() && newVec.size() < THRESH){
		if(dest[ptr1] > src[ptr2]){
			__append(dest[ptr1]);
			ptr1++;
		}else{
			__append(src[ptr2]);
			ptr2++;
		}
	}
	while(newVec.size() < THRESH && ptr1 < dest.size()){
		__append(dest[ptr1]);
		ptr1++;
	}
	while(newVec.size() < THRESH && ptr2 < src.size()){
		__append(src[ptr2]);
		ptr2++;
	}
	for(auto u : newVec) __used[u.second] = false;
	swap(dest, newVec);
	newVec.clear();
}
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:3:1: error: 'vector' does not name a type
    3 | vector<int> ord;
      | ^~~~~~
bitaro.cpp:4:1: error: 'vector' does not name a type
    4 | vector<int> g[100005];
      | ^~~~~~
bitaro.cpp:5:1: error: 'vector' does not name a type
    5 | vector<int> rg[100005];
      | ^~~~~~
bitaro.cpp: In function 'void dfs(int)':
bitaro.cpp:10:14: error: 'g' was not declared in this scope
   10 |  for(int v : g[u]){
      |              ^
bitaro.cpp:13:2: error: 'ord' was not declared in this scope
   13 |  ord.push_back(u);
      |  ^~~
bitaro.cpp: At global scope:
bitaro.cpp:15:1: error: 'vector' does not name a type
   15 | vector<pair<int,int> > dp[100005]; // | dp[i] | <= THRESH.
      | ^~~~~~
bitaro.cpp:17:1: error: 'vector' does not name a type
   17 | vector<pair<int,int> > newVec;
      | ^~~~~~
bitaro.cpp:18:15: error: variable or field '__append' declared void
   18 | void __append(pair<int,int> x){
      |               ^~~~
bitaro.cpp:18:15: error: 'pair' was not declared in this scope
bitaro.cpp:1:1: note: 'std::pair' is defined in header '<utility>'; did you forget to '#include <utility>'?
  +++ |+#include <utility>
    1 | using namespace std;
bitaro.cpp:18:20: error: expected primary-expression before 'int'
   18 | void __append(pair<int,int> x){
      |                    ^~~
bitaro.cpp:18:24: error: expected primary-expression before 'int'
   18 | void __append(pair<int,int> x){
      |                        ^~~
bitaro.cpp:24:12: error: variable or field 'merge' declared void
   24 | void merge(vector<pair<int,int> >& dest, vector<pair<int,int> > src){
      |            ^~~~~~
bitaro.cpp:24:12: error: 'vector' was not declared in this scope
bitaro.cpp:1:1: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
  +++ |+#include <vector>
    1 | using namespace std;
bitaro.cpp:24:19: error: 'pair' was not declared in this scope
   24 | void merge(vector<pair<int,int> >& dest, vector<pair<int,int> > src){
      |                   ^~~~
bitaro.cpp:24:19: note: 'std::pair' is defined in header '<utility>'; did you forget to '#include <utility>'?
bitaro.cpp:24:24: error: expected primary-expression before 'int'
   24 | void merge(vector<pair<int,int> >& dest, vector<pair<int,int> > src){
      |                        ^~~
bitaro.cpp:24:28: error: expected primary-expression before 'int'
   24 | void merge(vector<pair<int,int> >& dest, vector<pair<int,int> > src){
      |                            ^~~
bitaro.cpp:24:42: error: 'vector' was not declared in this scope
   24 | void merge(vector<pair<int,int> >& dest, vector<pair<int,int> > src){
      |                                          ^~~~~~
bitaro.cpp:24:42: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
bitaro.cpp:24:49: error: 'pair' was not declared in this scope
   24 | void merge(vector<pair<int,int> >& dest, vector<pair<int,int> > src){
      |                                                 ^~~~
bitaro.cpp:24:49: note: 'std::pair' is defined in header '<utility>'; did you forget to '#include <utility>'?
bitaro.cpp:24:54: error: expected primary-expression before 'int'
   24 | void merge(vector<pair<int,int> >& dest, vector<pair<int,int> > src){
      |                                                      ^~~
bitaro.cpp:24:58: error: expected primary-expression before 'int'
   24 | void merge(vector<pair<int,int> >& dest, vector<pair<int,int> > src){
      |                                                          ^~~
bitaro.cpp: In function 'int recalculateAnswer(int)':
bitaro.cpp:52:14: error: 'ord' was not declared in this scope
   52 |  for(int u : ord){
      |              ^~~
bitaro.cpp:54:15: error: 'rg' was not declared in this scope
   54 |   for(int v : rg[u]){
      |               ^~
bitaro.cpp:55:15: error: 'max' was not declared in this scope
   55 |    subdp[u] = max(subdp[u], subdp[v]+1);
      |               ^~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:62:2: error: 'scanf' was not declared in this scope
   62 |  scanf("%d%d%d",&n,&m,&q);
      |  ^~~~~
bitaro.cpp:66:3: error: 'g' was not declared in this scope
   66 |   g[s].push_back(e);
      |   ^
bitaro.cpp:67:3: error: 'rg' was not declared in this scope
   67 |   rg[e].push_back(s);
      |   ^~
bitaro.cpp:70:10: error: 'ord' was not declared in this scope
   70 |  reverse(ord.begin(), ord.end());
      |          ^~~
bitaro.cpp:70:2: error: 'reverse' was not declared in this scope
   70 |  reverse(ord.begin(), ord.end());
      |  ^~~~~~~
bitaro.cpp:72:15: error: 'rg' was not declared in this scope
   72 |   for(int v : rg[u]){
      |               ^~
bitaro.cpp:73:10: error: 'dp' was not declared in this scope
   73 |    merge(dp[u], dp[v]);
      |          ^~
bitaro.cpp:73:4: error: 'merge' was not declared in this scope
   73 |    merge(dp[u], dp[v]);
      |    ^~~~~
bitaro.cpp:75:9: error: 'dp' was not declared in this scope
   75 |   merge(dp[u], {make_pair(-1, u)});
      |         ^~
bitaro.cpp:75:17: error: 'make_pair' was not declared in this scope
   75 |   merge(dp[u], {make_pair(-1, u)});
      |                 ^~~~~~~~~
bitaro.cpp:75:17: note: 'std::make_pair' is defined in header '<utility>'; did you forget to '#include <utility>'?
bitaro.cpp:75:3: error: 'merge' was not declared in this scope
   75 |   merge(dp[u], {make_pair(-1, u)});
      |   ^~~~~
bitaro.cpp:86:3: error: 'vector' was not declared in this scope
   86 |   vector<int> busy;
      |   ^~~~~~
bitaro.cpp:86:3: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
bitaro.cpp:86:10: error: expected primary-expression before 'int'
   86 |   vector<int> busy;
      |          ^~~
bitaro.cpp:87:3: error: 'busy' was not declared in this scope
   87 |   busy.reserve(y);
      |   ^~~~
bitaro.cpp:96:17: error: 'dp' was not declared in this scope; did you mean 'p'?
   96 |    for(auto p : dp[t]){
      |                 ^~
      |                 p
bitaro.cpp:105:3: error: 'printf' was not declared in this scope
  105 |   printf("%d\n",ans);
      |   ^~~~~~
bitaro.cpp:1:1: note: 'printf' is defined in header '<cstdio>'; did you forget to '#include <cstdio>'?
  +++ |+#include <cstdio>
    1 | using namespace std;