제출 #1072792

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1072792		Requiem	다리 (APIO19_bridges)	C++17	100 / 100	1264 ms	20388 KiB

bridges

#include<bits/stdc++.h>
#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 fi first
#define se second
#define pb push_back
#define endl '\n'
#define fast ios_base::sync_with_stdio(NULL), cin.tie(NULL), cout.tie(NULL)
#define ii pair<int, int>
#define iii pair<int, ii>
#define TASKNAME "bridges"
using namespace std;

/**
Cho do thi n dinh m canh.
Cay cau thu i co trong luong toi da la wi.
Ta co q truy van:
- Loai 1: Thay doi trong luong toi da cua cay cau thanh wi.
- Loai 2: Dem so luong thanh pho ma chiec xe co trong tai w co the di den tu thanh pho u.
n <= 5e4.

subtask 1: n <= 1000, q <= 1000, q <= 1e4.
Với mỗi truy vấn dựng cây khung với những cạnh có trọng số lớn hơn sqrt(w).

subtask 2: Cây đường thẳng.
Dùng walk on segment tree để tìm cái khoảng.

subtask 3: cây nhị phân hoàn hảo.

Độ cao của cây là 15.
Khi cập nhật cạnh thì ta cập nhật như thế nào.

Giả sử thằng cha của ta nằm ở tầng 7 trở lên thì khi đó ta sẽ có thể query trực tiếp tất cả các đỉnh
Số đỉnh nằm ở tầng 7 trở xuống là 256
Số đỉnh nằm trong 1 cây con ở tầng 7 trở lên 256.

Giả sử ta tìm được thằng bố thì khi nó ở tầng 7 trở lên thì ta duyệt bò được.
NẾu nó ở tầng 7 trở xuống thì ta sẽ duyệt đến những đỉnh mà nó có thể đến được mà độ sâu dưới 7, nếu như nó đến được thì tại đỉnh
đó ta cần lưu trước đáp án về 1 trọng số w.

Khi cập nhật lại thì đầu tiên là ta thay đổi trọng số cạnh, ta cần cập nhật đáp án cho các đỉnh ở tầng 8.
Nếu cập nhật cho 1 cạnh ở dưới tầng 8 thì ta không cần cập nhật nó.

Nếu cập nhật cho 1 cạnh ở tầng 8 trở lên thì ta nhận thấy kích thước cây con lúc này là nhỏ hơn 256 nên ta có thể cập nhật thủ công được.
Lưu kết quả vào cây BIT

subtask 4: Không có truy vấn loại 1:
Lúc này ta xử lý offline, thêm cạnh giảm dần.

subtask 5: Đồ thị là 1 cây.

subtask 6: Không còn ràng buộc gì.
GIả sử ta quay về cái approach nguyên thủy nhất:
Giả sử ta có trọng số w.
Dựng cây khung với những cạnh trọng số nhỏ hơn w.

Vấn đề của phương pháp này là khi ta xóa 1 cạnh thì ta không thể thêm vào được.
Giả sử ta chia cạnh thành sqrt(N) block thì ta chỉ cần dựng cây khung của sqrt(n) vùng thôi.

Solution chuẩn:
- Chia Block trên truy vấn. Giả sử ta có sqrt(N) block truy vấn.
- Trong block ta sẽ có 2 loại cạnh là cạnh thay đổi và cạnh không bị thay đổi.
Ta sẽ gọi cạnh bị thay đổi là cạnh đặc biệt.
Nhận xét của ta lúc này là kết quả của ta có thể được tính dựa vào những cạnh không thay đổi và sqrt(N) cạnh đặc biệt.

Ta cũng có các truy vấn hỏi.
Với từng truy vấn hỏi, tư tưởng của ta là ta sẽ kết hợp cả 2 loại cạnh thay đổi và không thay đổi.

Ta duyệt qua từng truy vấn:
- Nếu gặp truy vấn update thì ta sẽ đơn giản là chỉ cần thay đổi cạnh.
- Nếu gặp 1 truy vấn tính thì ta sẽ duyệt qua những cạnh đặc biệt. Nếu như TẠI THỜI ĐIỂM ĐÓ mà trọng số nó lớn hơn
thì ta thêm vào để lưu trữ.

Khi này ta duyệt như sau:
Ta duyệt những truy vấn tính theo thứ tự tăng dần:
- Với những cạnh không bị thay đổi mà có chi phí lớn hơn thì ta thêm vào.
- Đồng thời ta duyệt qua những cạnh đặc biệt thỏa mãn tại thời điểm đó.

TIP cài DSU rollback: nếu như muốn rollback thì hãy
**/

const int MAXN = 5e4 + 1;
const int MAXM = 1e5 + 9;
iii edge[MAXM];
int n, m, q;
struct BinaryIndexedTree{
    vector<int> BIT;
    int sz =0 ;
    BinaryIndexedTree(int _sz = 0){
        sz = _sz;
        BIT.resize(_sz + 9, 0);
    }
    int getDown(int id){
        int res = 0;
        assert(id <= sz);
        for(int i = id; i > 0; i -= i & (-i)) res += BIT[i];
        return res;
    }
    int getUp(int id){
        int res = 0;
        assert(id <= sz);
        for(int i = id; i <= sz; i += i & (-i))  res += BIT[i];
        return res;
    }
    void updDown(int id, int x){
        assert(id <= sz);
        for(int i = id; i > 0; i -= i & (-i)) BIT[i] += x;
    }

    void updUp(int id, int x){
        assert(id <= sz);
        for(int i = id; i <= sz; i += i & (-i)) BIT[i] += x;
    }
};
struct Question{
    int type, id, newLimit;
    int weightLimit;
} Query[MAXM];
struct DisjointSetUnion{
    vector<int> ranking, par;
    vector<ii> stk;
    DisjointSetUnion(int _sz = 0){
        par.resize(_sz + 9, 0);
        ranking.resize(_sz + 9, 0);
        iota(par.begin(), par.end(), 0);
        fill(ranking.begin(), ranking.end(), 1);
    }

    int root(int u){
        return (par[u] == u) ? u : root(par[u]);
    }

    void unite(int u, int v){
        u = root(u);
        v = root(v);
        if (u != v){
            if (ranking[u] < ranking[v]) swap(u, v);
            stk.pb({u, v});
            ranking[u] += ranking[v];
            par[v] = u;
        }
    }

    void rollback(){
        if (stk.size() == 0) return;
        int u = stk.back().fi;
        int v = stk.back().se;
        ranking[u] -= ranking[v];
        par[v] = v;
        stk.pop_back();
    }
};
namespace subtask1{
    bool check(){
        return n <= 1000 and m <= 2000 and q <= 10000;
    }

    void solve(){
        FOR(i, 0, q - 1){
            if (Query[i].type == 1){
                edge[Query[i].id].fi = Query[i].newLimit;
            }
            else{
                DisjointSetUnion DSU(n);
                FOR(j, 0, m - 1){
                    if (edge[j].fi >= Query[i].weightLimit){
                        DSU.unite(edge[j].se.fi, edge[j].se.se);
                    }
                }
                int res = DSU.ranking[DSU.root(Query[i].id)];
                printf("%lld \n", res);
            }
        }
    }
}

namespace subtask4{
    bool check(){
        if (__builtin_popcount(n + 1) == 1 and m == n - 1){
            FOR(i, 0, m - 1){
                int u = edge[i].se.fi + 1;
                int v = edge[i].se.se + 1;
                if (u != v / 2) return false;
            }
            return true;
        }
        return false;
    }

    const int THRESHOLD = 8;

    int depth[MAXN], par[MAXN]; //parEdge[i]: chi so cua canh di len bo.
    vector<int> g[MAXN];
    void fdfs(int u, int p){ //first dfs
        par[u] = p;
        for(auto id: g[u]){
            int v = edge[id].se.fi + edge[id].se.se - u;
            if (v == p) continue;
            fdfs(v, u);
        }
    }

    struct Subtree{
        vector<int> listVal;
        vector<int> listPath;

        int getVal(int x){
            return lower_bound(listVal.begin(), listVal.end(), x) - listVal.begin() + 1;
        }
        void dfs(int u, int p, int mnPath){
             listPath.pb(mnPath);
             listVal.pb(mnPath);
             for(auto id: g[u]){
                 int v = edge[id].se.fi + edge[id].se.se -u;
                 if (v == p) continue;
                 dfs(v, u, min(mnPath, edge[id].fi));
             }
        }

        void build(int node){
            dfs(node, par[node], 1e9 + 1);
            sort(listVal.begin(), listVal.end());
            listVal.erase(unique(listVal.begin(), listVal.end()), listVal.end());

//            FOR(i, 0, (int) listPath.size() - 1){
//                listPath[i] = getVal()
//            }
        }
    };
    void solve(){
        FOR(i, 0, n - 1){
            if (i == 0) depth[i] = 0;
            else depth[i] = depth[(i - 1) / 2] + 1;
        }

        FOR(i, 0, m - 1){
            g[edge[i].se.fi].pb(i);
            g[edge[i].se.se].pb(i);
        }

        fdfs(0, -1);

    }
}
namespace subtask6{
    bool check(){
        return true;
    }

    const int block = 1288;
    bool changed[MAXM];
    int answer[MAXM];
    vector<int> ask, upd, unchanged, toJoin[block + 20];
    /**
    ask: chi so cua nhung truy van tinh tona
    unchanged: chi so cua nhung canh khong thay doi.
    upd: Chi so cua nhung canh bi thay doi.
    **/
    void reset(){
        ask.clear();
        upd.clear();
        unchanged.clear();
    }

    void solve(){
        for(int l = 0; l < q; l += block){
            DisjointSetUnion DSU(n);
            memset(changed, false, sizeof(changed));
            int r = min(q - 1, l + block - 1);
            reset();
            FOR(i, l, r){
                if (Query[i].type == 1){
                    upd.pb(Query[i].id);
//                    printf("%lld \n", Query[i].id);
                    changed[Query[i].id] = true;
                }
                else {
                    ask.pb(i);
                }
            }

            FOR(i, 0, m - 1){
                if (!changed[i]) unchanged.pb(i);
            }

            FOR(i, l, r){
                if (Query[i].type == 1) {
                    edge[Query[i].id].fi = Query[i].newLimit;
                }
                else{
                    toJoin[i - l].clear();
                    for(auto t: upd){
                        if (edge[t].fi >= Query[i].weightLimit) {
                            toJoin[i - l].pb(t);
                        }
                    }
                }
            }
            sort(ask.begin(), ask.end(), [&](const int &a, const int &b){
                 return Query[a].weightLimit > Query[b].weightLimit;
            });

            sort(unchanged.begin(), unchanged.end(), [&](const int &a, const int &b){
                 return edge[a].fi < edge[b].fi;
            });

            for(auto id: ask){
                while(unchanged.size() > 0 and edge[unchanged.back()].fi >= Query[id].weightLimit){
                      DSU.unite(edge[unchanged.back()].se.fi, edge[unchanged.back()].se.se);
//                      printf("%lld \n", unchanged.back());
                      unchanged.pop_back();
                }
                int prv_size = DSU.stk.size();
                for(auto t: toJoin[id - l]) {
                    DSU.unite(edge[t].se.fi, edge[t].se.se);
//                    printf("%lld \n", t);
                }
                answer[id] = DSU.ranking[DSU.root(Query[id].id)];
                while(DSU.stk.size() > prv_size) DSU.rollback();
            }

        }

        FOR(i, 0, q - 1){
            if (Query[i].type == 2) printf("%lld \n", answer[i]);
        }
    }
}
main(){
    fast;
    if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }
    cin >> n >> m;
    FOR(i, 0, m - 1){
        cin >> edge[i].se.fi >> edge[i].se.se >> edge[i].fi;
        edge[i].se.se--;
        edge[i].se.fi--;
    }
    cin >> q;
    FOR(i, 0, q - 1){
        cin >> Query[i].type;
        if (Query[i].type == 1){
            cin >> Query[i].id >> Query[i].newLimit;
        }
        else {
            cin >> Query[i].id >> Query[i].weightLimit;
        }
        Query[i].id--;
    }
//    if (subtask1::check()) return subtask1::solve(), 0;
    if (subtask6::check()) return subtask6::solve(), 0;

}

컴파일 시 표준 에러 (stderr) 메시지

bridges.cpp: In function 'void subtask1::solve()':
bridges.cpp:171:28: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
  171 |                 printf("%lld \n", res);
      |                         ~~~^      ~~~
      |                            |      |
      |                            |      int
      |                            long long int
      |                         %d
bridges.cpp: In function 'void subtask6::solve()':
bridges.cpp:319:38: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  319 |                 while(DSU.stk.size() > prv_size) DSU.rollback();
      |                       ~~~~~~~~~~~~~~~^~~~~~~~~~
bridges.cpp:325:48: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
  325 |             if (Query[i].type == 2) printf("%lld \n", answer[i]);
      |                                             ~~~^      ~~~~~~~~~
      |                                                |              |
      |                                                long long int  int
      |                                             %d
bridges.cpp: At global scope:
bridges.cpp:329:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  329 | main(){
      | ^~~~
bridges.cpp: In function 'int main()':
bridges.cpp:332:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  332 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:333:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  333 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 27 / 27