oj.uz

Submission #765853

# Submission time Handle Problem Language Result Execution time Memory
765853 2023-06-25T06:34:57 Z sentheta Werewolf (IOI18_werewolf) C++17
15 / 100
 168 ms 21272 KB 
#include "werewolf.h"
// author : sentheta aka vanwij
#ifdef VANWIJ
	#include"/home/user/code/bits/stdc++.h"
#else
	#include"bits/stdc++.h"
#endif
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;

const int N = 3005;

int n, m, q;
V<int> adj[N];

V<int> ans;

int l, r, tar;
bool vis[N][2];
bool dfs(int x,int t){
	// cout << x _ t << nl;
	if(t==1 && r<x) return 0;
	if(t==0 && x<l) return 0;
	if(vis[x][t]) return 0;
	vis[x][t] = 1;


	if(x==tar && t==1) return 1;
	if(t==0 && l<=x && x<=r && dfs(x,1)){
		return 1;
	}
	for(int y : adj[x]){
		if(dfs(y,t)) return 1;
	}
	return 0;
}

V<int> check_validity(int _n,V<int>_u, V<int>_v,
							V<int>_s, V<int>_e,V<int>_l,V<int>_r){
	n = _n; m = _u.size(); q = _s.size();
	ans = V<int>(q);

	rep(i,0,m){
		adj[_u[i]].push_back(_v[i]);
		adj[_v[i]].push_back(_u[i]);
	}

	rep(i,0,q){
		rep(x,0,n) rep(t,0,2) vis[x][t] = 0;

		l = _l[i];
		r = _r[i];
		tar = _e[i];
		ans[i] = dfs(_s[i], 0);
	}

	return ans;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 91 ms 644 KB Output is correct
11 Correct 71 ms 716 KB Output is correct
12 Correct 14 ms 776 KB Output is correct
13 Correct 80 ms 736 KB Output is correct
14 Correct 67 ms 648 KB Output is correct
15 Correct 168 ms 860 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 91 ms 21272 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 91 ms 644 KB Output is correct
11 Correct 71 ms 716 KB Output is correct
12 Correct 14 ms 776 KB Output is correct
13 Correct 80 ms 736 KB Output is correct
14 Correct 67 ms 648 KB Output is correct
15 Correct 168 ms 860 KB Output is correct
16 Runtime error 91 ms 21272 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -