Submission #1072761

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072761		Requiem	Bridges (APIO19_bridges)	C++17	100 / 100	2493 ms	10392 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 1 block, ta chia làm 2 loại cạnh: cạnh cố định và cạnh bị thay đổi.

- Ta sort những cạnh bị thay đổi và truy vấn tính toán theo chiều giảm dần.
Từ đó ta dễ dàng tính được những đỉnh đến được từ u thông qua những cạnh không đổi đó.

Bây giờ ta đi vào xử lý truy vấn:
+ Với 1 truy vấn update, ta đơn giản là cập nhật cạnh.
+ Với 1 truy vấn tính, ta duyệt qua những cạnh đã bị thay đổi, nếu trọng lượng của nó lớn hơn w thì ta có thể nối 2 cạnh xong ta phải rollback DSU của ta về.
Với 1 truy vấn tính, ta sẽ tốn không quá O(sqrt(n) * log).
Để bỏ log đi thì ta có thể nối cạnh vào xong bắt đầu DFS. Ta cũng sẽ không đi qua quá sqrt(n) đỉnh.

**/

const int MAXN = 5e4 + 1;
const int MAXM = 1e5 + 9;
iii edge[MAXM];
int n, m, q;

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 subtask6{
    bool check(){
        return true;
    }

    const int block = 512;
    bool changed[MAXM];
    int answer[MAXM];
    vector<int> ask, upd, unchanged, toJoin[560];
    /**
    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;

}

Compilation message (stderr)

bridges.cpp: In function 'void subtask1::solve()':
bridges.cpp:136:28: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
  136 |                 printf("%lld \n", res);
      |                         ~~~^      ~~~
      |                            |      |
      |                            |      int
      |                            long long int
      |                         %d
bridges.cpp: In function 'void subtask6::solve()':
bridges.cpp:215: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]
  215 |                 while(DSU.stk.size() > prv_size) DSU.rollback();
      |                       ~~~~~~~~~~~~~~~^~~~~~~~~~
bridges.cpp:221:48: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
  221 |             if (Query[i].type == 2) printf("%lld \n", answer[i]);
      |                                             ~~~^      ~~~~~~~~~
      |                                                |              |
      |                                                long long int  int
      |                                             %d
bridges.cpp: At global scope:
bridges.cpp:225:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  225 | main(){
      | ^~~~
bridges.cpp: In function 'int main()':
bridges.cpp:228:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  228 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:229:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  229 |         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