Submission #116663

#	Time	Username	Problem	Language	Result	Execution time	Memory
116663		Sorting	Werewolf (IOI18_werewolf)	C++14	15 / 100	4048 ms	39492 KiB

werewolf

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 7;

vector<int> adj[MAXN], ans;
pair<bool, int> dp[MAXN][2];
int to, l, r, idx;

bool solve(int u, bool stage){
	pair<bool, int> &p = dp[u][stage];

	if(p.second == idx){
		return p.first;
	}
	if(u == to){
		if(stage || (u >= l &&  u <= r)){
			return true;
		}
		return false;
	}
	if(!stage && u < l){
		return false;
	}
	if(stage && u > r){
		return false;
	}

	p.second = idx;
	p.first = false;

	if(!stage && u <= r){
		if(solve(u, true)){
			p.first = true;

			return true;
		}
	}

	for(int v: adj[u]){
		if(solve(v, stage)){
			p.first = true;

			return true;
		}
	}

	return false;
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
	for(int i = 0; i < X.size(); i++){
		adj[X[i]].push_back(Y[i]);
		adj[Y[i]].push_back(X[i]);
	}

	for(int i = 0; i < S.size(); i++){
		to = E[i];
		l = L[i];
		r = R[i];

		idx = i + 1;

		ans.push_back(solve(S[i], false));
	}

	return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:53:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < X.size(); i++){
                 ~~^~~~~~~~~~
werewolf.cpp:58:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < S.size(); i++){
                 ~~^~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51