Submission #934384

#	Time	Username	Problem	Language	Result	Execution time	Memory
934384		haxorman	Bridges (APIO19_bridges)	C++14	13 / 100	3084 ms	31176 KiB

bridges

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

const int mxN = 1e5 + 7;
const int SZ = exp2(ceil(log2(mxN)));
 
int dsu[mxN], ans[mxN], ind[mxN];
vector<pair<int,pair<int,int>>> add[4 * mxN], edges;
 
int find(int x) {
    return dsu[x] < 0 ? x : find(dsu[x]);
}
 
array<int,3> unite(int x, int y) {
    x = find(x), y = find(y);
 
    if (x == y) return {0, 0, 0};
 
    if (dsu[x] > dsu[y]) {
        swap(x, y);
    }
    array<int,3> rev = {x, y, dsu[y]};
 
    dsu[x] += dsu[y];
    dsu[y] = x;
    return rev;
}
 
void update(int& lo, int& hi, pair<int,pair<int,int>> ed, int ind=1, int l=1, int r=SZ) {
    if (lo > r || l > hi) {
        return;
    }
 
    if (lo <= l && r <= hi) {
        add[ind].push_back(ed);
        return;
    }
 
    int mid = (l + r) / 2;
    update(lo, hi, ed, 2 * ind, l, mid);
    update(lo, hi, ed, 2 * ind + 1, mid + 1, r);
}
 
void query(int& pos, int& node, int& mn, int ind=1, int l=1, int r=SZ) {
    vector<array<int,3>> rem;
    for (auto ed : add[ind]) {
        int w = ed.first;
        auto [u, v] = ed.second;
        //cout << u << ' ' << v << ' ' << w << "\n";
        if (w >= mn) {
            rem.push_back(unite(u, v));

            if (!rem.back()[0]) {
                rem.pop_back();
            }
        }
    }
 
    int mid = (l + r) / 2;
    if (l == r) {
        ans[pos] = -dsu[find(node)];
    }
    else if (pos <= mid) {
        query(pos, node, mn, 2*ind, l, mid);
    }
    else {
        query(pos, node, mn, 2*ind+1, mid+1, r);
    }
 
    for (int i = rem.size() - 1; i >= 0; --i) {
        dsu[rem[i][0]] -= rem[i][2];
        dsu[rem[i][1]] = rem[i][2];
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    memset(dsu, -1, sizeof(dsu));
    int n, m;
    cin >> n >> m;
    
    edges.push_back({0, {0, 0}});
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;

        edges.push_back({w,{u,v}});
        ind[i] = 1;
    }

    int q;
    cin >> q;
    
    vector<pair<int,pair<int,int>>> check;
    for (int i = 1; i <= q; ++i) {
        int t;
        cin >> t;

        if (t == 1) {
            int pos, w;
            cin >> pos >> w;
            
            update(ind[pos], i, edges[pos]);
            edges[pos].first = w;
            ind[pos] = i+1;
        }
        else {
            int node, w;
            cin >> node >> w;

            check.push_back({i, {node, w}});
        }
    }
    
    for (int i = 1; i <= m; ++i) {
        update(ind[i], q, edges[i]);
    }
    
    for (auto que : check) {
        int pos = que.first;
        auto [node, mn] = que.second;
        query(pos, node, mn);
        for (int i = 0; i < mxN; ++i) {
            assert(dsu[i] == -1);
        }
        cout << ans[que.first] << "\n";
    }
}

Compilation message (stderr)

bridges.cpp: In function 'void query(int&, int&, int&, int, int, int)':
bridges.cpp:48:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |         auto [u, v] = ed.second;
      |              ^
bridges.cpp: In function 'int32_t main()':
bridges.cpp:122:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  122 |         auto [node, mn] = que.second;
      |              ^

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