#include "werewolf.h"
#include<bits/stdc++.h>
//#define int long long
#define endl '\n'
#define fast ios_base::sync_with_stdio(NULL), cin.tie(NULL), cout.tie(NULL)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define TASKNAME "werewolf"
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
/**
Cho đồ thị n đỉnh, m cạnh.
Ta có q truy vấn: Si Ei Li Ri.
Ta cần di chuyển từ Si dến Ei sao cho:
Ta có 2 trạng thái:
trạng thái 1: ta không được đi qua các đỉnh có chỉ số nhỏ hơn Li.
trạng thái 2: Ta không được đi qua các đỉnh có chỉ số lớn hơn Ri.
Ta bắt buộc phải chuyển trạng thái 1 lần trên đường đi tại các đỉnh từ Li đến Ri.
Ban đầu ta ở trạng thái 1.
subtask 1(7%): n <= 100, m <= 200, q <= 100
Từ Li ta sẽ dựng dược các tplt mà trạng thái 1 có thể di chuyển được.
Tử Ri ta sẽ dụng được các tplt mà trạng thái 2 có thể di chuyển được.
Từ Si ta sẽ tìm 1 đỉnh thuộc đoạn [Li, Ri] để chuyển trạng thái xong ta kiểm tra xem ta có thể di chuyển
từ đó đến Ei bằng cách bfs.
đpt: O(q * m * n)
subtask 2(8%): n <= 3000, m <= 6000, q <= 3000
Tối ưu từ subtask 1:
Thay vì phải tìm đường đi một cách thủ công thì ta có thể dùng ctdl dsu để trả lời nhanh hơn
subtask 3(31%): cây đường thẳng.
Đường đi của ta có dạng Si(0), v2(0) v3(0) ... vi(0) -> vi(1)... Ei(1)
Gọi VL là tập những đỉnh mà ta có thể đến được từ Si và đi qua những đỉnh lớn hơn Li.
Gọi VR là tập những đỉnh mà ta có thể đến được từ Ri và đi qua những đỉnh nhỏ hơn Ri.
Nếu như S = VL giao VR khác rỗng thì ta có thể đến được. (ta coi như là bfs 2 đầu)
Nhận xét của ta là VL và VR đều là những đoạn thẳng
Thì với 1 truy vấn, ta có thể sử dụng RMQ để giải và tìm VL và VR.
1 cách tiếp cận khác là dùng DSU?
Với truy vấn i, ta sẽ muốn biết (Si, Li) là vị trí xa nhất mà ta có thể đi được với các số đều không nhỏ hơn Li.
Tương tự ta cũng sẽ giải với truy vấn với (Ei, Ri). Thì ta sẽ có được cái đoạn đó. Từ đó ta sẽ tìm được giao điểm.
subtask 4(51%): điều kiện gốc.
Kế thừa ý tưởng từ subtask 3.
Dựng 2 cây reachbility Tree với trọng số cạnh là max của 2 đầu và min của 2 đầu.
Khi này ta sẽ tìm được các đoạn 2D mà Si và Ri quản lý. Kết hợp với các CTDL 2D thì ta có thể giải được cái giao điểm.
**/
const int MAXN = 6e6 + 9;
struct Question{
int start, dest, l, r, id;
} query[MAXN];
int numNode, numEdge, numQuery;
ii edge[MAXN];
struct DisjointSetUnion{
vector<int> lab;
DisjointSetUnion(int _sz = 0){
lab.resize(_sz + 9, -1);
fill(lab.begin(), lab.end(), -1);
}
int root(int u){
return ((lab[u] < 0) ? u : lab[u] = root(lab[u]));
}
bool unite(int u, int v){
u = root(u);
v = root(v);
if (u != v){
lab[u] += lab[v];
lab[v] = u;
return true;
}
return false;
}
};
struct BinaryIndexedTree{
vector<int> BIT;
int _sz = 0;
BinaryIndexedTree(int _n = 0){
_sz = _n;
BIT.resize(_sz + 9, 0);
}
int get(int id){
int res = 0;
for(int i = id; i > 0; i -= i & (-i)){
res += BIT[i];
}
return res;
}
void upd(int id, int x){
for(int i = id; i <= _sz; i += i & (-i)){
BIT[i] += x;
}
}
};
struct XY2D{
vector<ii> point; //cac diem can kiem tra.
vector<pair<ii, ii>> rect;
vector<pair<ii,ii>> eventPoint;
vector<int> answer, mark;
int numEventPoint = 0;
vector<int> countPoint; //voi moi diem ta dem coi co bao nhieu diem ma co Xj <= Xi, Yj <= Yi.
vector<int> listVal;
int getVal(int x){
return lower_bound(listVal.begin(), listVal.end(), x) - listVal.begin() + 1;
}
//rectangle chua 2 x1 < x2, y1 < y2.
vector<int> countPointInRect(vector<pair<ii,ii>> &rectangle, vector<ii> &pts){
point = pts;
rect= rectangle;
BinaryIndexedTree BIT(800000);
FOR(i, 0, point.size() - 1){
eventPoint.pb({point[i], {numEventPoint++, -1}});
}
mark.resize(rect.size());
FOR(i, 0, rect.size() - 1){
int x1 = rect[i].fi.fi;
int y1 = rect[i].fi.se;
int x2 = rect[i].se.fi;
int y2 = rect[i].se.se;
mark[i] = numEventPoint;
eventPoint.pb({{x1 - 1, y1 - 1}, {numEventPoint++, i}});
eventPoint.pb({{x2, y1 - 1}, {numEventPoint++, i}});
eventPoint.pb({{x1 - 1, y2}, {numEventPoint++, i}});
eventPoint.pb({{x2, y2},{numEventPoint++, i}});
}
sort(eventPoint.begin(), eventPoint.end(), [&](const pair<ii, ii> &a, const pair<ii, ii> &b){
return ((a.fi.fi == b.fi.fi) ? ((a.fi.se == b.fi.se) ? a.se.se < b.se.se : a.fi.se < b.fi.se) : (a.fi.fi < b.fi.fi));
});
FOR(i, 0, numEventPoint - 1){
listVal.pb(eventPoint[i].fi.fi);
listVal.pb(eventPoint[i].fi.se);
}
countPoint.resize(numEventPoint);
sort(listVal.begin(), listVal.end());
listVal.erase(unique(listVal.begin(), listVal.end()), listVal.end());
FOR(i, 0, numEventPoint - 1){
// printf("PTS %lld %lld %lld %d\n", eventPoint[i].fi.fi, eventPoint[i].fi.se, eventPoint[i].se.fi, eventPoint[i].se.se);
eventPoint[i].fi.fi = getVal(eventPoint[i].fi.fi);
eventPoint[i].fi.se = getVal(eventPoint[i].fi.se);
}
for(int i = 0; i < eventPoint.size(); i++){
if (eventPoint[i].se.se != -1){
int id = eventPoint[i].se.fi;
countPoint[id] += BIT.get(eventPoint[i].fi.se);
// printf("Query %d\n", eventPoint[i].fi.se);
// printf("%d\n", countPoint[id]);
}
if (eventPoint[i].se.se == -1) {
// printf("UPD %d\n", eventPoint[i].fi.se);
BIT.upd(eventPoint[i].fi.se, 1);
}
}
// printf("\n");
answer.resize(rect.size());
// FOR(i, 0, numEventPoint - 1){
// printf("%d \n", countPoint[i]);
// }
FOR(i, 0, rect.size() - 1){
answer[i] = countPoint[mark[i] + 3] - countPoint[mark[i] + 1] - countPoint[mark[i] + 2] + countPoint[mark[i]];
}
return answer;
}
};
namespace subtask1{
bool check(){
return numNode <= 3000 and numEdge <= 6000;
}
bool solve(int S, int E, int L, int R){
DisjointSetUnion Left(numNode), Right(numNode);
FOR(i, 0, numEdge - 1){
if (edge[i].fi >= L and edge[i].se >= L) Left.unite(edge[i].fi, edge[i].se);
}
FOR(i, 0, numEdge - 1){
if (edge[i].fi <= R and edge[i].se <= R) Right.unite(edge[i].fi, edge[i].se);
}
FOR(i, 0, numNode - 1){
if (Left.root(i) == Left.root(S) and Right.root(i) == Right.root(E)) return true;
}
return false;
}
}
struct reachabilityTree{
vector<vector<int>> reachTree;
vector<vector<int>> P;
vector<ii> listEdge;
vector<int> in, out, etour;
void dfs(int u, int p){
in[u] = etour.size();
etour.pb(u);
P[0][u] = p;
for(auto v: reachTree[u]){
if (v == p) continue;
dfs(v, u);
}
out[u] = etour.size() - 1;
}
void init(){
in.resize(numNode + numEdge);
out.resize(numNode + numEdge);
reachTree.resize(numNode + numEdge);
P.resize(30, vector<int>(numNode + numEdge, -1));
}
int jumpLeft(int u, int lb){
int res = 0;
FORD(i, 20, 0){
if (P[i][u] != -1 and min(listEdge[P[i][u] - numNode].fi, listEdge[P[i][u] - numNode].se) >= lb) {
u = P[i][u];
}
}
return u; //tim dinh xa nhat ve phia tren sao cho no la nhung dinh den duoc tu u thong qua nhung canh lon hon lb
}
int jumpRight(int u, int rb){
int res = 0;
FORD(i, 20, 0){
if (P[i][u] != -1 and max(listEdge[P[i][u] - numNode].fi, listEdge[P[i][u] - numNode].se) <= rb) {
u = P[i][u];
}
}
return u; //tim dinh xa nhat ve phia tren sao cho no la nhung dinh den duoc tu u thong qua nhung canh nho hon rb.
}
void build(ii edge[]){
DisjointSetUnion DSU(numNode + numEdge);
init();
FOR(i, 0, numEdge - 1){
int u = edge[i].fi;
int v = edge[i].se;
listEdge.pb({u, v});
int rt1 = DSU.root(u);
int rt2 = DSU.root(v);
if (DSU.unite(i + numNode, rt1)){
// printf("RT: %lld %lld\n", i + numNode, rt1);
reachTree[i + numNode].pb(rt1);
}
if (DSU.unite(i + numNode, rt2)){
// printf("RT: %lld %lld\n", i + numNode, rt2);
reachTree[i + numNode].pb(rt2);
}
}
FORD(i, numEdge + numNode - 1, 0){
if (!in[i]) dfs(i, -1);
}
// FOR(i, 0, etour.size() - 1){
// printf("%lld ", etour[i]);
// }
// printf("\n");
FOR(i, 1, 20){
FOR(j, 0, numNode + numEdge - 1){
if (P[i - 1][j] == -1) P[i][j] = -1;
else P[i][j] = P[i - 1][P[i - 1][j]];
// printf("%d ", P[i][j]);
}
// printf("\n");
}
}
} leftTree, rightTree;
namespace subtask2{
bool check(){
return true;
}
void solve(vector<int> &A){
sort(edge, edge + numEdge, [&](const ii &a, const ii &b){
return min(a.fi, a.se) > min(b.se, b.fi);
});
// FOR(i, 0, numEdge - 1){
// printf("%lld %lld\n", edge[i].fi, edge[i].se);
// }
leftTree.build(edge);
sort(edge, edge + numEdge, [&](const ii &a, const ii &b){
return max(a.fi, a.se) < max(b.se, b.fi);
});
// FOR(i, 0, numEdge - 1){
// printf("%lld %lld\n", edge[i].fi, edge[i].se);
// }
rightTree.build(edge);
vector<pair<ii, ii>> listRect;
vector<ii> listPoint;
FOR(i, 0, numQuery - 1){
int start = query[i].start;
int dest = query[i].dest;
int lb = query[i].l;
int rb = query[i].r;
int u = leftTree.jumpLeft(start, lb);
int l1 = leftTree.in[u], r1 = leftTree.out[u];
// printf("%d %d %d\n", u, l1, r1);
int v = rightTree.jumpRight(dest, rb);
int l2 = rightTree.in[v], r2 = rightTree.out[v];
// printf("%d %d %d\n", v, l2, r2);
listRect.pb({{l1, l2}, {r1, r2}});
}
FOR(i, 0, numNode - 1){
listPoint.pb(ii(leftTree.in[i], rightTree.in[i]));
}
XY2D solution;
vector<int> result = solution.countPointInRect(listRect, listPoint);
for(int i = 0; i < result.size(); i++){
A[i] = result[i] > 0;
}
}
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
numNode = N;
numEdge = X.size();
numQuery = S.size();
FOR(i, 0, numEdge - 1){
edge[i] = ii(X[i], Y[i]);
}
FOR(i, 0, numQuery - 1){
query[i] = {S[i], E[i], L[i], R[i], i};
}
std::vector<int> A(numQuery);
if (subtask2::check()){
subtask2::solve(A);
}
return A;
}
Compilation message
werewolf.cpp: In member function 'std::vector<int> XY2D::countPointInRect(std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >&, std::vector<std::pair<int, int> >&)':
werewolf.cpp:6:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
6 | #define FOR(i, a, b) for(int i = a; i <= b; i++)
......
137 | FOR(i, 0, point.size() - 1){
| ~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:137:9: note: in expansion of macro 'FOR'
137 | FOR(i, 0, point.size() - 1){
| ^~~
werewolf.cpp:6:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
6 | #define FOR(i, a, b) for(int i = a; i <= b; i++)
......
141 | FOR(i, 0, rect.size() - 1){
| ~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:141:9: note: in expansion of macro 'FOR'
141 | FOR(i, 0, rect.size() - 1){
| ^~~
werewolf.cpp:169:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
169 | for(int i = 0; i < eventPoint.size(); i++){
| ~~^~~~~~~~~~~~~~~~~~~
werewolf.cpp:6:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
6 | #define FOR(i, a, b) for(int i = a; i <= b; i++)
......
188 | FOR(i, 0, rect.size() - 1){
| ~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:188:9: note: in expansion of macro 'FOR'
188 | FOR(i, 0, rect.size() - 1){
| ^~~
werewolf.cpp: In member function 'int reachabilityTree::jumpLeft(int, int)':
werewolf.cpp:241:13: warning: unused variable 'res' [-Wunused-variable]
241 | int res = 0;
| ^~~
werewolf.cpp: In member function 'int reachabilityTree::jumpRight(int, int)':
werewolf.cpp:251:13: warning: unused variable 'res' [-Wunused-variable]
251 | int res = 0;
| ^~~
werewolf.cpp: In function 'void subtask2::solve(std::vector<int>&)':
werewolf.cpp:345:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
345 | for(int i = 0; i < result.size(); i++){
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5724 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5724 KB |
Output is correct |
| 3 |
Correct |
2 ms |
5724 KB |
Output is correct |
| 4 |
Correct |
2 ms |
5556 KB |
Output is correct |
| 5 |
Correct |
2 ms |
5724 KB |
Output is correct |
| 6 |
Correct |
2 ms |
5724 KB |
Output is correct |
| 7 |
Correct |
2 ms |
5724 KB |
Output is correct |
| 8 |
Correct |
4 ms |
5720 KB |
Output is correct |
| 9 |
Correct |
2 ms |
5724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5724 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5724 KB |
Output is correct |
| 3 |
Correct |
2 ms |
5724 KB |
Output is correct |
| 4 |
Correct |
2 ms |
5556 KB |
Output is correct |
| 5 |
Correct |
2 ms |
5724 KB |
Output is correct |
| 6 |
Correct |
2 ms |
5724 KB |
Output is correct |
| 7 |
Correct |
2 ms |
5724 KB |
Output is correct |
| 8 |
Correct |
4 ms |
5720 KB |
Output is correct |
| 9 |
Correct |
2 ms |
5724 KB |
Output is correct |
| 10 |
Correct |
11 ms |
8664 KB |
Output is correct |
| 11 |
Correct |
9 ms |
8388 KB |
Output is correct |
| 12 |
Correct |
14 ms |
8556 KB |
Output is correct |
| 13 |
Correct |
10 ms |
8664 KB |
Output is correct |
| 14 |
Correct |
10 ms |
8408 KB |
Output is correct |
| 15 |
Correct |
12 ms |
9688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
717 ms |
201928 KB |
Output is correct |
| 2 |
Correct |
821 ms |
205304 KB |
Output is correct |
| 3 |
Correct |
721 ms |
203004 KB |
Output is correct |
| 4 |
Correct |
673 ms |
201976 KB |
Output is correct |
| 5 |
Correct |
675 ms |
201920 KB |
Output is correct |
| 6 |
Correct |
776 ms |
201980 KB |
Output is correct |
| 7 |
Correct |
622 ms |
202144 KB |
Output is correct |
| 8 |
Correct |
744 ms |
205340 KB |
Output is correct |
| 9 |
Correct |
594 ms |
203004 KB |
Output is correct |
| 10 |
Correct |
530 ms |
201928 KB |
Output is correct |
| 11 |
Correct |
556 ms |
201912 KB |
Output is correct |
| 12 |
Correct |
539 ms |
201932 KB |
Output is correct |
| 13 |
Correct |
789 ms |
205052 KB |
Output is correct |
| 14 |
Correct |
804 ms |
205008 KB |
Output is correct |
| 15 |
Correct |
827 ms |
205292 KB |
Output is correct |
| 16 |
Correct |
786 ms |
205560 KB |
Output is correct |
| 17 |
Correct |
599 ms |
201976 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5724 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5724 KB |
Output is correct |
| 3 |
Correct |
2 ms |
5724 KB |
Output is correct |
| 4 |
Correct |
2 ms |
5556 KB |
Output is correct |
| 5 |
Correct |
2 ms |
5724 KB |
Output is correct |
| 6 |
Correct |
2 ms |
5724 KB |
Output is correct |
| 7 |
Correct |
2 ms |
5724 KB |
Output is correct |
| 8 |
Correct |
4 ms |
5720 KB |
Output is correct |
| 9 |
Correct |
2 ms |
5724 KB |
Output is correct |
| 10 |
Correct |
11 ms |
8664 KB |
Output is correct |
| 11 |
Correct |
9 ms |
8388 KB |
Output is correct |
| 12 |
Correct |
14 ms |
8556 KB |
Output is correct |
| 13 |
Correct |
10 ms |
8664 KB |
Output is correct |
| 14 |
Correct |
10 ms |
8408 KB |
Output is correct |
| 15 |
Correct |
12 ms |
9688 KB |
Output is correct |
| 16 |
Correct |
717 ms |
201928 KB |
Output is correct |
| 17 |
Correct |
821 ms |
205304 KB |
Output is correct |
| 18 |
Correct |
721 ms |
203004 KB |
Output is correct |
| 19 |
Correct |
673 ms |
201976 KB |
Output is correct |
| 20 |
Correct |
675 ms |
201920 KB |
Output is correct |
| 21 |
Correct |
776 ms |
201980 KB |
Output is correct |
| 22 |
Correct |
622 ms |
202144 KB |
Output is correct |
| 23 |
Correct |
744 ms |
205340 KB |
Output is correct |
| 24 |
Correct |
594 ms |
203004 KB |
Output is correct |
| 25 |
Correct |
530 ms |
201928 KB |
Output is correct |
| 26 |
Correct |
556 ms |
201912 KB |
Output is correct |
| 27 |
Correct |
539 ms |
201932 KB |
Output is correct |
| 28 |
Correct |
789 ms |
205052 KB |
Output is correct |
| 29 |
Correct |
804 ms |
205008 KB |
Output is correct |
| 30 |
Correct |
827 ms |
205292 KB |
Output is correct |
| 31 |
Correct |
786 ms |
205560 KB |
Output is correct |
| 32 |
Correct |
599 ms |
201976 KB |
Output is correct |
| 33 |
Correct |
779 ms |
202748 KB |
Output is correct |
| 34 |
Correct |
776 ms |
228692 KB |
Output is correct |
| 35 |
Correct |
883 ms |
213080 KB |
Output is correct |
| 36 |
Correct |
743 ms |
204240 KB |
Output is correct |
| 37 |
Correct |
854 ms |
209088 KB |
Output is correct |
| 38 |
Correct |
807 ms |
207800 KB |
Output is correct |
| 39 |
Correct |
841 ms |
208624 KB |
Output is correct |
| 40 |
Correct |
949 ms |
287668 KB |
Output is correct |
| 41 |
Correct |
693 ms |
205776 KB |
Output is correct |
| 42 |
Correct |
558 ms |
204240 KB |
Output is correct |
| 43 |
Correct |
965 ms |
251940 KB |
Output is correct |
| 44 |
Correct |
753 ms |
208320 KB |
Output is correct |
| 45 |
Correct |
716 ms |
212280 KB |
Output is correct |
| 46 |
Correct |
727 ms |
208568 KB |
Output is correct |
| 47 |
Correct |
853 ms |
206988 KB |
Output is correct |
| 48 |
Correct |
846 ms |
205560 KB |
Output is correct |
| 49 |
Correct |
809 ms |
207060 KB |
Output is correct |
| 50 |
Correct |
843 ms |
205548 KB |
Output is correct |
| 51 |
Correct |
836 ms |
287364 KB |
Output is correct |
| 52 |
Correct |
881 ms |
287464 KB |
Output is correct |
