Submission #685880

#	Time	Username	Problem	Language	Result	Execution time	Memory
685880		Ninja_Kunai	Werewolf (IOI18_werewolf)	C++14	15 / 100	271 ms	30780 KiB

werewolf

/**
*    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[2][MAXN], cur;

	void dfs(int type, int u, int i) {
		if (dd[type][u] == cur) return;
		//cout << u << ' ' << trans << '\n';
		dd[type][u] = cur;

		for (auto v : adj[u]) {
			if (type == 0 && v >= q[i].l) {
				dfs(type, v, i);
			}

			if (type == 1 && v <= q[i].r) {
				dfs(type, v, i);
			}
		}
	}

	vector <int> solve() {
		vector <int> tmp;
		FOR(i, 1, nquery) {
			++cur;
			dfs(0, q[i].s, i);
			dfs(1, q[i].t, i);
			bool ok = 0;
			REP(j, n) if (dd[0][j] == cur && dd[1][j] == cur) {
				ok = 1;
				break;
			}

			if (ok) 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: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51