Submission #860045

#	Time	Username	Problem	Language	Result	Execution time	Memory
860045		TahirAliyev	Bridges (APIO19_bridges)	C++17	0 / 100	3049 ms	13364 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>

const int MAX = 1e5 + 5, BLOCK = 400;

struct E{
    int a, b, w, id;
};

int par[MAX];
vector<array<int, 4>> op;

int get(int node){
    if(par[node] < 0){
        return node;
    }
    return get(par[node]);
}

void unite(int u, int v, bool tolist = false){
    u = get(u), v = get(v);
    if(u == v) return;
    if(-par[u] < -par[v]){
        swap(u, v);
    }
    if(tolist){
        op.push_back({u, v, par[u], par[v]});
    }
    par[u] += par[v];
    par[v] = u;
}

void rollback(){
    while(!op.empty()){
        array<int, 4> a = op.back();
        op.pop_back();
        par[a[0]] = a[2];
        par[a[1]] = a[3];
    }
}

int n, m, q;

vector<E> edges;
array<int, 3> queries[MAX];
int ans[MAX];

vector<E> ed;
vector<array<int, 3>> s;
vector<int> updated[MAX];
vector<int> updates;

bool comp(E a, E b){
    return a.w < b.w;
}

void clean(){
    memset(par, -1, sizeof(par));
    memset(updated, 0, sizeof(updated));
    ed = edges;
    op.clear();
    sort(ed.rbegin(), ed.rend(), comp);
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        E e;
        cin >> e.a >> e.b >> e.w;
        e.id = i;
        edges.push_back(e);
    }
    cin >> q;
    for(int i = 1; i <= q; i++){
        cin >> queries[i][0] >> queries[i][1] >> queries[i][2];
    }

    for(int i = 1; i <= q; i += BLOCK){
        clean();
        for(int j = i; j <= i + BLOCK - 1 && j <= q; j++){
            if(queries[j][0] == 2){
                s.push_back({queries[j][2], queries[j][1], j});
            }
            else{
                if(updated[queries[j][1]].empty()){
                    updates.push_back(queries[j][1]);
                }
                updated[queries[j][1]].push_back(j);
            }
        }

        sort(s.rbegin(), s.rend());
        auto itr = ed.begin();
        for(auto a : s){
            while(itr != ed.end() && itr->w >= a[0]){
                if(updated[itr->id].empty()){
                    unite(itr->a, itr->b);
                }
                itr++;
            }
            for(int p : updates){
                int b = -1;
                for(int u : updated[p]){
                    if(u < a[2]){
                        b = u;
                    }
                }
                if(b == -1){
                    if(edges[p - 1].w >= a[0]){
                        unite(edges[p - 1].a, edges[p - 1].b, 1);
                    }
                }
                else{
                    if(queries[b][2] >= a[0]){
                        unite(edges[p - 1].a, edges[p - 1].b, 1);
                    }
                }
            }
            ans[a[2]] = -par[get(a[1])];
            rollback();
        }
        for(int u : updates){
            edges[queries[u][1] - 1].w = queries[u][2];
        }
    }

    for(int i = 1; i <= q; i++){
        if(queries[i][0] == 1) continue; 
        cout << ans[i] << '\n';
    }
}

Compilation message (stderr)

bridges.cpp: In function 'void clean()':
bridges.cpp:62:39: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'class std::vector<int>' with no trivial copy-assignment; use assignment or value-initialization instead [-Wclass-memaccess]
   62 |     memset(updated, 0, sizeof(updated));
      |                                       ^
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/functional:62,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from bridges.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:389:11: note: 'class std::vector<int>' declared here
  389 |     class vector : protected _Vector_base<_Tp, _Alloc>
      |           ^~~~~~

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