#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#include "grader.cpp"
#endif
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
Tran The Bao
CTL - Da Lat
Cay ngay cay dem nhung deo duoc cong nhan
*/
struct Edge {
int u, v, w;
Edge() {}
Edge(int u, int v, int w) : u(u), v(v), w(w) {}
};
bool cmp(Edge &a, Edge &b) { return a.w < b.w; }
bool cmp1(Edge &a, Edge &b) { return a.w > b.w; }
struct Query {
int s, e, l, id;
Query() {}
Query(int s, int e, int l, int id) : s(s), e(e), l(l), id(id) {}
};
const int N = 2e5 + 5;
int n, q, p[N], pos[N], mine[N][18], LOG[N];
vpi d[N];
multiset<int> s[N];
vector<Edge> e, e1;
vector<Query> query[N];
int getp(int x) { return x == p[x]? x : p[x] = getp(p[x]); }
void join(int x, int y, int w) {
x = getp(x);
y = getp(y);
if (x == y) return;
if (sz(d[x]) < sz(d[y])) swap(x, y);
d[x].back().nd = w;
EACH(i, d[y]) d[x].pb(i);
d[y].clear();
p[y] = x;
}
void join(int x, int y) {
x = getp(x);
y = getp(y);
if (x == y) return;
if (sz(s[x]) < sz(s[y])) swap(x, y);
EACH(i, s[y]) s[x].insert(i);
s[y].clear();
p[y] = x;
}
int get(int l, int r) {
if (l > r) swap(l, r);
--r;
int len = LOG[r - l + 1];
return min(mine[l][len], mine[r - (1 << len) + 1][len]);
}
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
n = N;
q = sz(S);
vi ans(q, 0);
int m = sz(X);
FOR(i, 0, m - 1) {
int u = X[i], v = Y[i], w = max(u, v), w1 = min(u, v);
e.pb(Edge(u, v, w));
e1.pb(Edge(u, v, w1));
}
FOR(i, 0, q - 1) {
int s = S[i], e = E[i], l = L[i], r = R[i];
query[r].pb(Query(s, e, l, i));
}
FOR(i, 0, n - 1) {
p[i] = i;
d[i].pb({i, i});
}
sort(all(e), cmp);
sort(all(e1), cmp1);
EACH(i, e1) {
int u = i.u, v = i.v, w = i.w;
join(u, v, w);
}
vpi a1 = d[getp(0)];
FOR(i, 0, n - 1) {
pos[a1[i].st] = i;
mine[i][0] = a1[i].nd;
}
FOR(i, 1, n) LOG[i] = log2(i);
FOR(j, 1, 17)
FOR(i, 0, n - 1) {
if (i + (1 << j) > n - 1) continue;
int a = mine[i][j - 1], b = mine[i + (1 << (j - 1))][j - 1];
mine[i][j] = min(a, b);
}
FOR(i, 0, n - 1) {
p[i] = i;
s[i].insert(pos[i]);
}
int l = 0;
FOR(i, 0, n - 1) {
WHILE(l < sz(e) && e[l].w <= i) {
join(e[l].u, e[l].v);
++l;
}
EACH(j, query[i]) {
int s = j.s, e = j.e, l = j.l, id = j.id;
if (s <= i && e <= i) {
if (s >= l) ans[id] = getp(s) == getp(e);
continue;
}
if (s >= l && e >= l) {
ans[id] = get(pos[s], pos[e]) >= l;
continue;
}
if (s < e) continue;
swap(s, e);
int root = getp(s), maxr = -1;
multiset<int> &s1 = ::s[root];
if (*--s1.end() >= pos[e]) {
int pos1 = pos[e], pos2 = *s1.lb(pos[e]);
maxr = max(maxr, get(pos1, pos2));
if (s1.lb(pos[e]) != s1.begin()) {
int pos2 = *--s1.lb(pos[e]);
maxr = max(maxr, get(pos1, pos2));
}
}
else {
int pos1 = pos[e], pos2 = *--s1.end();
maxr = max(maxr, get(pos1, pos2));
}
if (maxr >= l) ans[id] = 1;
}
}
return ans;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/
Compilation message
werewolf.cpp: In function 'void join(int, int, int)':
werewolf.cpp:28:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
28 | #define EACH(i, x) for (auto &(i) : (x))
| ^
werewolf.cpp:63:5: note: in expansion of macro 'EACH'
63 | EACH(i, d[y]) d[x].pb(i);
| ^~~~
werewolf.cpp: In function 'void join(int, int)':
werewolf.cpp:28:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
28 | #define EACH(i, x) for (auto &(i) : (x))
| ^
werewolf.cpp:72:5: note: in expansion of macro 'EACH'
72 | EACH(i, s[y]) s[x].insert(i);
| ^~~~
werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
werewolf.cpp:87:5: note: in expansion of macro 'FOR'
87 | FOR(i, 0, m - 1) {
| ^~~
werewolf.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
werewolf.cpp:92:5: note: in expansion of macro 'FOR'
92 | FOR(i, 0, q - 1) {
| ^~~
werewolf.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
werewolf.cpp:96:5: note: in expansion of macro 'FOR'
96 | FOR(i, 0, n - 1) {
| ^~~
werewolf.cpp:28:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
28 | #define EACH(i, x) for (auto &(i) : (x))
| ^
werewolf.cpp:102:5: note: in expansion of macro 'EACH'
102 | EACH(i, e1) {
| ^~~~
werewolf.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
werewolf.cpp:107:5: note: in expansion of macro 'FOR'
107 | FOR(i, 0, n - 1) {
| ^~~
werewolf.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
werewolf.cpp:111:5: note: in expansion of macro 'FOR'
111 | FOR(i, 1, n) LOG[i] = log2(i);
| ^~~
werewolf.cpp:26:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
werewolf.cpp:112:5: note: in expansion of macro 'FOR'
112 | FOR(j, 1, 17)
| ^~~
werewolf.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
werewolf.cpp:113:5: note: in expansion of macro 'FOR'
113 | FOR(i, 0, n - 1) {
| ^~~
werewolf.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
werewolf.cpp:118:5: note: in expansion of macro 'FOR'
118 | FOR(i, 0, n - 1) {
| ^~~
werewolf.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
werewolf.cpp:123:5: note: in expansion of macro 'FOR'
123 | FOR(i, 0, n - 1) {
| ^~~
werewolf.cpp:28:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
28 | #define EACH(i, x) for (auto &(i) : (x))
| ^
werewolf.cpp:128:9: note: in expansion of macro 'EACH'
128 | EACH(j, query[i]) {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
666 ms |
89256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
