oj.uz

Submission #685837

# Submission time Handle Problem Language Result Execution time Memory
685837 2023-01-25T01:59:50 Z Ninja_Kunai Werewolf (IOI18_werewolf) C++14
0 / 100
 205 ms 39240 KB 
/**
*    Author :  Nguyen Tuan Vu
*    Created : 25.01.2023
**/

#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define MASK(x) ((1ll)<<(x))
#define BIT(x, i) (((x)>>(i))&(1))
#define ALL(v)  (v).begin(), (v).end()
#define REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define FORD(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i)
#define db(val) "["#val" = "<<(val)<<"] "

template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

using namespace std;

mt19937 jdg(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) {return l + jdg() % (r - l + 1);}

const int MAXN = 4e5 + 5;
int n, m, nquery;
pair <int, int> edges[MAXN];
vector <int> adj[MAXN];

struct QUERY {
	int s, t, l, r;
	// constraints : 
	// For each query i : 0 <= i < Q
	// 0 <= l(i) <= s(i) <= n - 1
	// 0 <= e(i) <= r(i) <= n - 1
	// s(i) != e(i)
	// l(i) <= r(i)

	QUERY() {}
	QUERY(int s, int t, int l, int r) {
		this->s = s;
		this->t = t;
		this->l = l;
		this->r = r;
	}
} q[MAXN];

namespace sub2 {
	int dd[MAXN], cur;

	void dfs(int u, int id) {
		//cout << u << ' ';
		dd[u] = cur;
		if (dd[q[id].t] == cur) return;

		for (auto v : adj[u]) if (dd[v] != cur) {
			if (q[id].l <= u && u <= q[id].r) {
				dfs(v, id);
			}
			else if (u > q[id].r && v >= q[id].l) {
				dfs(v, id);
			}
			else if (u < q[id].l && v <= q[id].r) {
				dfs(v, id);
			}
		}
	}

	vector <int> solve() {
		vector <int> tmp;
		FOR(i, 1, nquery) {
			++cur;
			dfs(q[i].s, i);

			if (dd[q[i].t] == cur) tmp.push_back(1);
			else tmp.push_back(0);
		}

		return tmp;
	}
};

vector <int> check_validity(int N, vector <int> X, vector <int> Y, vector <int> S, vector <int> T, vector <int> L, vector <int> R) {
	n = N; m = X.size(); nquery = S.size();
	REP(i, m) {
		edges[i + 1] = make_pair(X[i], Y[i]);
		adj[X[i]].push_back(Y[i]);
		adj[Y[i]].push_back(X[i]);
	}

	REP(i, nquery) q[i + 1] = QUERY(S[i], T[i], L[i], R[i]);

	if (n <= 3000 && m <= 6000 && nquery <= 3000) return sub2::solve();
	return vector <int> (nquery, 0);
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Incorrect 6 ms 9740 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Incorrect 6 ms 9740 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Incorrect 6 ms 9740 KB Output isn't correct
3 Halted 0 ms 0 KB -