//#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 = 3e5 + 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(1000000);
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 |
2 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
2 ms |
6236 KB |
Output is correct |
| 5 |
Correct |
2 ms |
6464 KB |
Output is correct |
| 6 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 7 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 8 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 9 |
Correct |
2 ms |
6492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
2 ms |
6236 KB |
Output is correct |
| 5 |
Correct |
2 ms |
6464 KB |
Output is correct |
| 6 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 7 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 8 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 9 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 10 |
Correct |
10 ms |
9432 KB |
Output is correct |
| 11 |
Correct |
10 ms |
9176 KB |
Output is correct |
| 12 |
Correct |
9 ms |
9172 KB |
Output is correct |
| 13 |
Correct |
11 ms |
9432 KB |
Output is correct |
| 14 |
Correct |
10 ms |
9308 KB |
Output is correct |
| 15 |
Correct |
11 ms |
10452 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
709 ms |
200972 KB |
Output is correct |
| 2 |
Correct |
773 ms |
204296 KB |
Output is correct |
| 3 |
Correct |
696 ms |
201932 KB |
Output is correct |
| 4 |
Correct |
654 ms |
201480 KB |
Output is correct |
| 5 |
Correct |
675 ms |
201360 KB |
Output is correct |
| 6 |
Correct |
697 ms |
201740 KB |
Output is correct |
| 7 |
Correct |
613 ms |
200968 KB |
Output is correct |
| 8 |
Correct |
731 ms |
204300 KB |
Output is correct |
| 9 |
Correct |
573 ms |
202184 KB |
Output is correct |
| 10 |
Correct |
516 ms |
201432 KB |
Output is correct |
| 11 |
Correct |
537 ms |
200968 KB |
Output is correct |
| 12 |
Correct |
537 ms |
201160 KB |
Output is correct |
| 13 |
Correct |
831 ms |
203788 KB |
Output is correct |
| 14 |
Correct |
850 ms |
203980 KB |
Output is correct |
| 15 |
Correct |
814 ms |
204520 KB |
Output is correct |
| 16 |
Correct |
812 ms |
204512 KB |
Output is correct |
| 17 |
Correct |
604 ms |
201432 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
2 ms |
6236 KB |
Output is correct |
| 5 |
Correct |
2 ms |
6464 KB |
Output is correct |
| 6 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 7 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 8 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 9 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 10 |
Correct |
10 ms |
9432 KB |
Output is correct |
| 11 |
Correct |
10 ms |
9176 KB |
Output is correct |
| 12 |
Correct |
9 ms |
9172 KB |
Output is correct |
| 13 |
Correct |
11 ms |
9432 KB |
Output is correct |
| 14 |
Correct |
10 ms |
9308 KB |
Output is correct |
| 15 |
Correct |
11 ms |
10452 KB |
Output is correct |
| 16 |
Correct |
709 ms |
200972 KB |
Output is correct |
| 17 |
Correct |
773 ms |
204296 KB |
Output is correct |
| 18 |
Correct |
696 ms |
201932 KB |
Output is correct |
| 19 |
Correct |
654 ms |
201480 KB |
Output is correct |
| 20 |
Correct |
675 ms |
201360 KB |
Output is correct |
| 21 |
Correct |
697 ms |
201740 KB |
Output is correct |
| 22 |
Correct |
613 ms |
200968 KB |
Output is correct |
| 23 |
Correct |
731 ms |
204300 KB |
Output is correct |
| 24 |
Correct |
573 ms |
202184 KB |
Output is correct |
| 25 |
Correct |
516 ms |
201432 KB |
Output is correct |
| 26 |
Correct |
537 ms |
200968 KB |
Output is correct |
| 27 |
Correct |
537 ms |
201160 KB |
Output is correct |
| 28 |
Correct |
831 ms |
203788 KB |
Output is correct |
| 29 |
Correct |
850 ms |
203980 KB |
Output is correct |
| 30 |
Correct |
814 ms |
204520 KB |
Output is correct |
| 31 |
Correct |
812 ms |
204512 KB |
Output is correct |
| 32 |
Correct |
604 ms |
201432 KB |
Output is correct |
| 33 |
Correct |
805 ms |
201676 KB |
Output is correct |
| 34 |
Runtime error |
129 ms |
40532 KB |
Execution killed with signal 11 |
| 35 |
Halted |
0 ms |
0 KB |
- |
