oj.uz

Submission #831570

# Submission time Handle Problem Language Result Execution time Memory
831570 2023-08-20T10:29:14 Z caganyanmaz Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 37092 KB 
#include <bits/stdc++.h>
#define pb push_back
#include "werewolf.h"

//#define DEBUGGING
#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif
constexpr static int MXN = 3e5;
constexpr static int MXST = MXN<<1;
constexpr static int INF = 1e6;

using namespace std;
bitset<MXN> visited[2];
vector<int> g[MXN];

bool valid(int node, int l, int r, int state)
{
	return (state == 0 && node >= l) || (state == 1 && node <= r);
}

bool dfs(int node, int t, int l, int r, int state)
{
	visited[state][node] = true;
	if (!valid(node, l, r, state))
		return false;
	debug(node, t, l, r, state);
	if (state == 1 && node == t)
		return true;
	if (!visited[1][node] && dfs(node, t, l, r, 1))
		return true;
	for (int c : g[node])
		if (!visited[state][c] && dfs(c, t, l, r, state))
			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++)
	{
		g[x[i]].pb(y[i]);
		g[y[i]].pb(x[i]);
	}
	vector<int> res(s.size());
	for (int i = 0; i < s.size(); i++)
	{
		debug("--------");
		visited[0].reset();
		visited[1].reset();
		res[i] = dfs(s[i], e[i], L[i], R[i], 0);
	}
	return res;
	

}

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:42:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for (int i = 0; i < x.size(); i++)
      |                  ~~^~~~~~~~~~
werewolf.cpp:48:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for (int i = 0; i < s.size(); i++)
      |                  ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7352 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 3 ms 7380 KB Output is correct
7 Correct 3 ms 7380 KB Output is correct
8 Correct 3 ms 7380 KB Output is correct
9 Correct 3 ms 7344 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7352 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 3 ms 7380 KB Output is correct
7 Correct 3 ms 7380 KB Output is correct
8 Correct 3 ms 7380 KB Output is correct
9 Correct 3 ms 7344 KB Output is correct
10 Correct 112 ms 7764 KB Output is correct
11 Correct 81 ms 7764 KB Output is correct
12 Correct 15 ms 7892 KB Output is correct
13 Correct 106 ms 7816 KB Output is correct
14 Correct 80 ms 7760 KB Output is correct
15 Correct 161 ms 7928 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4032 ms 37092 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7352 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 3 ms 7380 KB Output is correct
7 Correct 3 ms 7380 KB Output is correct
8 Correct 3 ms 7380 KB Output is correct
9 Correct 3 ms 7344 KB Output is correct
10 Correct 112 ms 7764 KB Output is correct
11 Correct 81 ms 7764 KB Output is correct
12 Correct 15 ms 7892 KB Output is correct
13 Correct 106 ms 7816 KB Output is correct
14 Correct 80 ms 7760 KB Output is correct
15 Correct 161 ms 7928 KB Output is correct
16 Execution timed out 4032 ms 37092 KB Time limit exceeded
17 Halted 0 ms 0 KB -