Submission #97312

#	Time	Username	Problem	Language	Result	Execution time	Memory
97312		E869120	Werewolf (IOI18_werewolf)	C++14	15 / 100	424 ms	19704 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

int N, M, Q, dp[5009][2]; vector<int>G[5009];

vector<int> check_validity(int NN, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	N = NN; M = X.size(); Q = S.size();
	for (int i = 0; i < M; i++) { G[X[i]].push_back(Y[i]); G[Y[i]].push_back(X[i]); }
	
	vector<int>ans;
	
	for (int i = 0; i < Q; i++) {
		for (int j = 0; j <= N; j++) { dp[j][0] = 0; dp[j][1] = 0; }
		dp[S[i]][0] = 1; queue<pair<int, int>> que; que.push(make_pair(S[i], 0));
		
		while(!que.empty()){
			int pos1 = que.front().first, pos2 = que.front().second; que.pop();
			
			if (pos2 == 0 && dp[pos1][1] == 0 && L[i] <= pos1 && pos1 <= R[i]) {
				dp[pos1][1] = 1;
				que.push(make_pair(pos1, 1));
			}
			
			for (int j = 0; j < G[pos1].size(); j++) {
				int to = G[pos1][j];
				if (pos2 == 0 && to < L[i]) continue;
				if (pos2 == 1 && R[i] < to) continue;
				if (dp[to][pos2] == 1) continue;
				dp[to][pos2] = 1;
				que.push(make_pair(to, pos2));
			}
		}
		
		ans.push_back(dp[E[i]][1]);
	}
	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:25:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < G[pos1].size(); j++) {
                    ~~^~~~~~~~~~~~~~~~

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