Submission #340129

#	Time	Username	Problem	Language	Result	Execution time	Memory
340129		rocks03	Bridges (APIO19_bridges)	C++14	100 / 100	2309 ms	5624 KiB

bridges

#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;
    };
};

vector<int> p, sz;
vector<pii> rollback;
void init(int n){
    p.resize(n);
    iota(all(p), 0);
    sz.resize(n);
    fill(all(sz), 1);
    rollback.clear();
}
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];
}

const int MAXM = 1e5+100;
const int MAXQ = 1e5+100;
int N, M, ans[MAXQ];
Edge e[MAXM], e2[MAXM];
bool used[MAXM];

void solve(){
    cin >> N >> M;
    for(int i = 0; i < M; i++){
        cin >> e2[i].u >> e2[i].v >> e2[i].w;
    }
    int Q; cin >> Q;
    const int BLOCK = 1000;
    vector<Query1> v1;
    vector<Query2> v2;
    for(int q = 0; q < Q; q += BLOCK){
        for(int i = 0; i < M; i++){
            e[i] = {e2[i].u, e2[i].v, e2[i].w, i};
        }
        sort(e, e+M);
        int l = q, r = min(Q, l + BLOCK) - 1;
        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;
        init(N + 1);
        for(auto [qs, qw, qt] : v2){
            while(ind < M && e[ind].w >= qw){
                if(!used[e[ind].i]){
                    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(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(unite(e2[uj].u, e2[uj].v)){
                            cnt++;
                        }
                    }
                    used[uj] = false;
                }
            }
            ans[qt] = query(qs);
            while(cnt--) roll_back();
            for(auto [uj, uw, ut] : v1){
                used[uj] = true;
            }
        }
        reverse(all(v1));
        for(auto [uj, uw, ut] : v1){
            e2[uj].w = uw;
            used[uj] = false;
        }
        v1.clear();
        v2.clear();
    }
    for(int i = 0; i < Q; i++){
        if(ans[i]){
            cout << ans[i] << "\n";
        }
    }
}

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

Compilation message (stderr)

bridges.cpp: In function 'void roll_back()':
bridges.cpp:52:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |     auto [a, b] = rollback.back();
      |          ^
bridges.cpp: In function 'void solve()':
bridges.cpp:101:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  101 |         for(auto [qs, qw, qt] : v2){
      |                  ^
bridges.cpp:109:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  109 |             for(auto [uj, uw, ut] : v1){
      |                      ^
bridges.cpp:121:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  121 |             for(auto [uj, uw, ut] : v1){
      |                      ^
bridges.cpp:133:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  133 |             for(auto [uj, uw, ut] : v1){
      |                      ^
bridges.cpp:138:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  138 |         for(auto [uj, uw, ut] : v1){
      |                  ^

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