oj.uz

Submission #97311

# Submission time Handle Problem Language Result Execution time Memory
97311 2019-02-15T03:37:25 Z E869120 Werewolf (IOI18_werewolf) C++14
0 / 100
 248 ms 28028 KB 
#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 < N; 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 = 1; 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

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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 248 ms 28028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -