oj.uz

Submission #766666

# Submission time Handle Problem Language Result Execution time Memory
766666 2023-06-26T04:02:02 Z marvinthang Werewolf (IOI18_werewolf) C++17
100 / 100
 569 ms 95592 KB 
/*************************************
*    author: marvinthang             *
*    created: 26.06.2023 10:38:52    *
*************************************/

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int 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; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

// end of template

vector<int> check_validity(int N, vector <int> X, vector <int> Y, vector <int> S, vector <int> E, vector <int> L, vector <int> R) {
	int M = X.size();
	int Q = S.size();
	vector <int> lab(N, -1);
	vector <vector <int>> adj(N), L_at(N), R_at(N), tree_adj(N);

	REP(i, M) {
		adj[X[i]].push_back(Y[i]);
		adj[Y[i]].push_back(X[i]);
	}

	REP(i, Q) {
		L_at[L[i]].push_back(i);
		R_at[R[i]].push_back(i);
	}

	function <int(int)> find = [&] (int u) {
		return lab[u] < 0 ? u : lab[u] = find(lab[u]);
	};

	int nw = N;
	REPD(i, N) {
		int u;
		for (int v: adj[i]) if (v >= i) {
			if ((u = find(i)) == (v = find(v))) continue;
			if (lab[u] > lab[v]) swap(u, v);

			lab.push_back(lab[u] + lab[v]);
			lab[u] = lab[v] = nw++;
			tree_adj.push_back(vector<int> {u, v});
		}
		for (int id: L_at[i]) S[id] = find(S[id]);
	}

	int timeDfs = 0;
	vector <int> tin(nw), tout(nw);
	function <void(int)> dfs = [&] (int u) {
		tin[u] = ++timeDfs;
		for (int v: tree_adj[u]) dfs(v);
		tout[u] = timeDfs;
	};
	dfs(nw - 1);
	lab.assign(N, -1);
	vector <set <int>> s(N);

	vector <int> res(Q);
	REP(i, N) {
		int u;
		s[i].insert(tin[i]);
		for (int v: adj[i]) if (v <= i) {
			if ((u = find(i)) == (v = find(v))) continue;
			if (s[u].size() < s[v].size()) swap(u, v);
			lab[u] += lab[v];
			lab[v] = u;
			for (int x: s[v]) s[u].insert(x);
			s[v].clear();
		}
		for (int id: R_at[i]) {
			auto it = s[find(E[id])].lower_bound(tin[S[id]]);
			res[id] = it != s[find(E[id])].end() && *it <= tout[S[id]];
		}
	}
	return res;
}

#ifdef LOCAL
#include <cstdio>
#include <cstdlib>
#include <vector>
#include "werewolf.h"

namespace {

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

}  // namespace

int main() {
	file("werewolf");
  int N = read_int();
  int M = read_int();
  int Q = read_int();
  std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
  for (int j = 0; j < M; ++j) {
    X[j] = read_int();
    Y[j] = read_int();
  }
  for (int i = 0; i < Q; ++i) {
    S[i] = read_int();
    E[i] = read_int();
    L[i] = read_int();
    R[i] = read_int();
  }

  std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
  for (size_t i = 0; i < A.size(); ++i) {
    printf("%d\n", A[i]);
  }
  return 0;
}
#endif

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 5 ms 1620 KB Output is correct
11 Correct 5 ms 1492 KB Output is correct
12 Correct 5 ms 1492 KB Output is correct
13 Correct 4 ms 1492 KB Output is correct
14 Correct 4 ms 1488 KB Output is correct
15 Correct 5 ms 1724 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 542 ms 88072 KB Output is correct
2 Correct 456 ms 86476 KB Output is correct
3 Correct 414 ms 84836 KB Output is correct
4 Correct 459 ms 84688 KB Output is correct
5 Correct 448 ms 84880 KB Output is correct
6 Correct 501 ms 85332 KB Output is correct
7 Correct 546 ms 85920 KB Output is correct
8 Correct 406 ms 86380 KB Output is correct
9 Correct 326 ms 83752 KB Output is correct
10 Correct 357 ms 83352 KB Output is correct
11 Correct 360 ms 83636 KB Output is correct
12 Correct 445 ms 85516 KB Output is correct
13 Correct 400 ms 95512 KB Output is correct
14 Correct 357 ms 95504 KB Output is correct
15 Correct 444 ms 95592 KB Output is correct
16 Correct 384 ms 95508 KB Output is correct
17 Correct 511 ms 85820 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 5 ms 1620 KB Output is correct
11 Correct 5 ms 1492 KB Output is correct
12 Correct 5 ms 1492 KB Output is correct
13 Correct 4 ms 1492 KB Output is correct
14 Correct 4 ms 1488 KB Output is correct
15 Correct 5 ms 1724 KB Output is correct
16 Correct 542 ms 88072 KB Output is correct
17 Correct 456 ms 86476 KB Output is correct
18 Correct 414 ms 84836 KB Output is correct
19 Correct 459 ms 84688 KB Output is correct
20 Correct 448 ms 84880 KB Output is correct
21 Correct 501 ms 85332 KB Output is correct
22 Correct 546 ms 85920 KB Output is correct
23 Correct 406 ms 86380 KB Output is correct
24 Correct 326 ms 83752 KB Output is correct
25 Correct 357 ms 83352 KB Output is correct
26 Correct 360 ms 83636 KB Output is correct
27 Correct 445 ms 85516 KB Output is correct
28 Correct 400 ms 95512 KB Output is correct
29 Correct 357 ms 95504 KB Output is correct
30 Correct 444 ms 95592 KB Output is correct
31 Correct 384 ms 95508 KB Output is correct
32 Correct 511 ms 85820 KB Output is correct
33 Correct 508 ms 82748 KB Output is correct
34 Correct 186 ms 29660 KB Output is correct
35 Correct 503 ms 86384 KB Output is correct
36 Correct 498 ms 81716 KB Output is correct
37 Correct 569 ms 85636 KB Output is correct
38 Correct 526 ms 82520 KB Output is correct
39 Correct 459 ms 81112 KB Output is correct
40 Correct 509 ms 91928 KB Output is correct
41 Correct 478 ms 84708 KB Output is correct
42 Correct 430 ms 80328 KB Output is correct
43 Correct 499 ms 90268 KB Output is correct
44 Correct 482 ms 85548 KB Output is correct
45 Correct 372 ms 81324 KB Output is correct
46 Correct 374 ms 80112 KB Output is correct
47 Correct 395 ms 91752 KB Output is correct
48 Correct 374 ms 91656 KB Output is correct
49 Correct 389 ms 91648 KB Output is correct
50 Correct 382 ms 91496 KB Output is correct
51 Correct 453 ms 91344 KB Output is correct
52 Correct 456 ms 91364 KB Output is correct