Submission #340122

#	Time	Username	Problem	Language	Result	Execution time	Memory
340122		rocks03	Bridges (APIO19_bridges)	C++14	27 / 100	3076 ms	7040 KiB

bridges

//#pragma GCC target("avx2")
//#pragma GCC optimization("O3")
//#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct Edge{
    int u, v, w, i;
    bool operator<(const Edge& other) const{
        return w > other.w;
    };
};
struct Query1{
    int uj, uw, ut;
};
struct Query2{
    int qs, qw, qt;
    bool operator<(const Query2& other) const{
        return qw > other.qw;
    };
};

class Dsu{
public:
    vector<int> p, sz;
    vector<pii> rollback;
    Dsu(int n){
        p.resize(n);
        iota(all(p), 0);
        sz.resize(n, 1);
    }
    int find(int x){
        if(x == p[x]) return x;
        return find(p[x]);
    }
    bool unite(int a, int b){
        a = find(a), b = find(b);
        if(a == b) return false;
        if(sz[a] < sz[b]) swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
        rollback.pb({a, b});
        return true;
    }
    void roll_back(){
        auto [a, b] = rollback.back();
        p[b] = b;
        sz[a] -= sz[b];
        rollback.pop_back();
    }
    int query(int x){
        x = find(x);
        return sz[x];
    }
};

void solve(){
    int N, M;
    cin >> N >> M;
    vector<Edge> e(M);
    for(int i = 0; i < M; i++){
        cin >> e[i].u >> e[i].v >> e[i].w;
        e[i].i = i;
    }
    vector<Edge> e2 = e;
    sort(all(e));
    int Q;
    cin >> Q;
    const int BLOCK = 100000;
    vector<bool> used(M, false);
    vector<int> ans(Q, -1);
    for(int q = 0; q < Q; q += BLOCK){
        int l = q, r = min(Q, l + BLOCK) - 1;
        vector<Query1> v1;
        vector<Query2> v2;
        for(int i = l; i <= r; i++){
            int t; cin >> t;
            if(t == 1){
                int j, w;
                cin >> j >> w;
                --j;
                used[j] = true;
                v1.pb({j, w, i});
            } else if(t == 2){
                int s, w;
                cin >> s >> w;
                v2.pb({s, w, i});
            }
        }
        reverse(all(v1));
        sort(all(v2));
        int ind = 0;
        Dsu G(N + 1);
        for(auto [qs, qw, qt] : v2){
            while(ind < M && e[ind].w >= qw){
                if(!used[e[ind].i]){
                    G.unite(e[ind].u, e[ind].v);
                }
                ind++;
            }
            int cnt = 0;
            for(auto [uj, uw, ut] : v1){
                if(ut < qt){
                    if(used[uj]){
                        if(uw >= qw){
                            if(G.unite(e2[uj].u, e2[uj].v)){
                                cnt++;
                            }
                        }
                        used[uj] = false;
                    }
                }
            }
            for(auto [uj, uw, ut] : v1){
                if(used[uj]){
                    if(e2[uj].w >= qw){
                        if(G.unite(e2[uj].u, e2[uj].v)){
                            cnt++;
                        }
                    }
                    used[uj] = false;
                }
            }
            ans[qt] = G.query(qs);
            while(cnt--) G.roll_back();
            for(auto [uj, uw, ut] : v1){
                used[uj] = true;
            }
        }
        reverse(all(v1));
        for(auto [uj, uw, ut] : v1){
            e[uj].w = uw;
            used[uj] = false;
        }
    }
    for(auto x : ans){
        if(x != -1)
            cout << x << "\n";
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

Compilation message (stderr)

bridges.cpp: In member function 'void Dsu::roll_back()':
bridges.cpp:55:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |         auto [a, b] = rollback.back();
      |              ^
bridges.cpp: In function 'void solve()':
bridges.cpp:103:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  103 |         for(auto [qs, qw, qt] : v2){
      |                  ^
bridges.cpp:111:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  111 |             for(auto [uj, uw, ut] : v1){
      |                      ^
bridges.cpp:123:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  123 |             for(auto [uj, uw, ut] : v1){
      |                      ^
bridges.cpp:135:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  135 |             for(auto [uj, uw, ut] : v1){
      |                      ^
bridges.cpp:140:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  140 |         for(auto [uj, uw, ut] : v1){
      |                  ^

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