oj.uz

Submission #1069011

# Submission time Handle Problem Language Result Execution time Memory
1069011 2024-08-21T14:28:08 Z Requiem Werewolf (IOI18_werewolf) C++17
100 / 100
 1045 ms 290584 KB 
#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 = 1e6 + 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++){
      |                        ~~^~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6488 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 6492 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 6488 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6488 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 6492 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 6488 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 11 ms 9432 KB Output is correct
11 Correct 10 ms 9300 KB Output is correct
12 Correct 9 ms 9332 KB Output is correct
13 Correct 10 ms 9432 KB Output is correct
14 Correct 10 ms 9308 KB Output is correct
15 Correct 12 ms 10456 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 720 ms 203028 KB Output is correct
2 Correct 800 ms 205768 KB Output is correct
3 Correct 698 ms 204200 KB Output is correct
4 Correct 700 ms 203468 KB Output is correct
5 Correct 683 ms 203984 KB Output is correct
6 Correct 728 ms 203276 KB Output is correct
7 Correct 621 ms 202672 KB Output is correct
8 Correct 763 ms 206544 KB Output is correct
9 Correct 635 ms 204336 KB Output is correct
10 Correct 581 ms 203484 KB Output is correct
11 Correct 598 ms 202764 KB Output is correct
12 Correct 589 ms 202764 KB Output is correct
13 Correct 867 ms 206040 KB Output is correct
14 Correct 843 ms 205848 KB Output is correct
15 Correct 915 ms 206120 KB Output is correct
16 Correct 839 ms 206348 KB Output is correct
17 Correct 649 ms 202700 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6488 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 6492 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 6488 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 11 ms 9432 KB Output is correct
11 Correct 10 ms 9300 KB Output is correct
12 Correct 9 ms 9332 KB Output is correct
13 Correct 10 ms 9432 KB Output is correct
14 Correct 10 ms 9308 KB Output is correct
15 Correct 12 ms 10456 KB Output is correct
16 Correct 720 ms 203028 KB Output is correct
17 Correct 800 ms 205768 KB Output is correct
18 Correct 698 ms 204200 KB Output is correct
19 Correct 700 ms 203468 KB Output is correct
20 Correct 683 ms 203984 KB Output is correct
21 Correct 728 ms 203276 KB Output is correct
22 Correct 621 ms 202672 KB Output is correct
23 Correct 763 ms 206544 KB Output is correct
24 Correct 635 ms 204336 KB Output is correct
25 Correct 581 ms 203484 KB Output is correct
26 Correct 598 ms 202764 KB Output is correct
27 Correct 589 ms 202764 KB Output is correct
28 Correct 867 ms 206040 KB Output is correct
29 Correct 843 ms 205848 KB Output is correct
30 Correct 915 ms 206120 KB Output is correct
31 Correct 839 ms 206348 KB Output is correct
32 Correct 649 ms 202700 KB Output is correct
33 Correct 865 ms 203488 KB Output is correct
34 Correct 847 ms 229624 KB Output is correct
35 Correct 907 ms 214492 KB Output is correct
36 Correct 757 ms 206020 KB Output is correct
37 Correct 834 ms 210024 KB Output is correct
38 Correct 798 ms 208060 KB Output is correct
39 Correct 883 ms 209360 KB Output is correct
40 Correct 1045 ms 290584 KB Output is correct
41 Correct 690 ms 206788 KB Output is correct
42 Correct 591 ms 205024 KB Output is correct
43 Correct 1014 ms 252780 KB Output is correct
44 Correct 838 ms 210100 KB Output is correct
45 Correct 707 ms 213984 KB Output is correct
46 Correct 715 ms 209412 KB Output is correct
47 Correct 831 ms 208352 KB Output is correct
48 Correct 834 ms 206600 KB Output is correct
49 Correct 840 ms 207724 KB Output is correct
50 Correct 841 ms 206336 KB Output is correct
51 Correct 822 ms 289764 KB Output is correct
52 Correct 835 ms 288268 KB Output is correct