oj.uz

Submission #425431

# Submission time Handle Problem Language Result Execution time Memory
425431 2021-06-13T03:30:42 Z Monchito Werewolf (IOI18_werewolf) C++17
7 / 100
 4000 ms 21636 KB 
#include "werewolf.h"
#include <cstring>
using namespace std;
using vi = vector<int>;

#define sz(x) (int)x.size()

const int MAXN = 2e5;

vi G[MAXN];
bool vis[MAXN], can;
int s, e, l, r;

void DFS(int u, int d, int t, bool& flag) {
	if(u == d) flag = true;
	vis[u] = true;
	
	for(int v : G[u]) {
		if(!vis[v]) {
			if(t == 0){
				if(v >= l) DFS(v, d, t, flag);
			} else {
				if(v <= r) DFS(v, d, t, flag);
			}
		}	
	}
}

vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
	for(int i=0; i<sz(X); i++) {
		int u = X[i], v = Y[i];
		G[u].push_back(v);
		G[v].push_back(u);
	}

	int Q = sz(S);
	vi ret(Q);

	for(int i=0; i<Q; i++) {
		s = S[i]; e = E[i]; l = L[i]; r = R[i];
		can = false;

		for(int i=0; i<N; i++) {
			if(i > r) continue;

			bool flag = false;	
			memset(vis, false, sizeof(vis));

			DFS(s, i, 0, flag);
			if(flag) {
				flag = false;
				memset(vis, false, sizeof(vis));

				DFS(i, e, 1, flag);
				if(flag) { can = true; break; }
			}
		}

		ret[i] = (can)? 1 : 0;
	}

	return ret;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 5068 KB Output is correct
2 Correct 38 ms 5068 KB Output is correct
3 Correct 8 ms 5068 KB Output is correct
4 Correct 7 ms 5164 KB Output is correct
5 Correct 32 ms 5152 KB Output is correct
6 Correct 31 ms 5068 KB Output is correct
7 Correct 27 ms 5184 KB Output is correct
8 Correct 48 ms 5164 KB Output is correct
9 Correct 29 ms 5112 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 5068 KB Output is correct
2 Correct 38 ms 5068 KB Output is correct
3 Correct 8 ms 5068 KB Output is correct
4 Correct 7 ms 5164 KB Output is correct
5 Correct 32 ms 5152 KB Output is correct
6 Correct 31 ms 5068 KB Output is correct
7 Correct 27 ms 5184 KB Output is correct
8 Correct 48 ms 5164 KB Output is correct
9 Correct 29 ms 5112 KB Output is correct
10 Execution timed out 4049 ms 5528 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 5068 KB Output is correct
2 Correct 38 ms 5068 KB Output is correct
3 Correct 8 ms 5068 KB Output is correct
4 Correct 7 ms 5164 KB Output is correct
5 Correct 32 ms 5152 KB Output is correct
6 Correct 31 ms 5068 KB Output is correct
7 Correct 27 ms 5184 KB Output is correct
8 Correct 48 ms 5164 KB Output is correct
9 Correct 29 ms 5112 KB Output is correct
10 Execution timed out 4049 ms 5528 KB Time limit exceeded
11 Halted 0 ms 0 KB -