Submission #1069007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069007		Requiem	Werewolf (IOI18_werewolf)	C++17	49 / 100	850 ms	204520 KiB

werewolf

//#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 (stderr)

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++){
      |                        ~~^~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 0 / 51