Submission #255876

#	Time	Username	Problem	Language	Result	Execution time	Memory
255876		balbit	Bridges (APIO19_bridges)	C++14	100 / 100	2673 ms	18424 KiB

bridges

#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

#define ll long long

#define pll pair<ll, ll>
#define pii pair<int, int>
#define f first
#define s second

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define pb push_back

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<" "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x ){ cerr<<x<<endl; }
template<typename T, typename ...S> void _do(T && x , S&&...y){ cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0),cin.tie(0)
#define endl '\n'
#define bug(...)
#endif // BALBIT

const int maxn = 5e4+100;

//vector<pii> g[maxn];

struct ed{
    int a,b,w;
};
int par[maxn], sz[maxn];
int find(int x) {return x == par[x]? x : par[x] = find(par[x]);}
void merge(int a, int b) {
    a = find(a), b = find(b);
    if (a==b)return;
    sz[b] += sz[a];
    par[a] = b;
}

struct ASK{
    int s,w,i;
};

const int bs = 800;

vector<int> g[maxn];

ll re = 0;
bool seen[maxn];
void DFS(int v) {
    bug(v);
    seen[v] = 1;
    re += sz[(v)];
    for (int u : g[v]) {
        if (!seen[u]) DFS(u);
    }
}

signed main(){
    IOS();
    int n,m; cin>>n>>m;
    vector<ed> v;
    for (int i = 0; i<m; ++i) {
        int a,b,w; cin>>a>>b>>w;
        --a; --b;
        v.pb({a,b,w});
    }
    int q; cin>>q;
    vector<int> ans(q);
    vector<int> tmp(m);
    for (int i = 0; i<q; i+=bs) {
        bug("HIIII");
        vector<int> idk(m,0);
        vector<int> dunno;
        vector<pair<pii, int> > chgq; // list of {changes,i}
        vector<ASK > ask;
        for (int j = i; j<min(i+bs, q); ++j) {
            int foo; cin>>foo;
            if (foo == 1) {
                int x,r; cin>>x>>r; --x;
                chgq.pb({{x,r},j});
                if (!idk[x]) dunno.pb(x);
                idk[x] = 1;
            }else{
                int s,w; cin>>s>>w; --s;
                ask.pb({s,w,j});
            }
        }
        for (int j = 0; j<n; ++j) par[j] = j, sz[j] = 1;
        vector<ed> V; V.reserve(m-SZ(dunno)+2);
        for (int j = 0; j<m; ++j) if (!idk[j]) V.pb(v[j]);

        sort(ALL(V),[&](ed a, ed b){return a.w > b.w;});
        int vit = 0;
        sort(ALL(ask), [&](ASK a, ASK b){return a.w > b.w;});
        for (ASK &a : ask) {
            while (vit < SZ(V) && V[vit].w >= a.w) {
//                if (!idk[vit]) {
                    merge(V[vit].a, V[vit].b);
//                }
                ++vit;
            }
            for (int x : dunno) tmp[x] = v[x].w;
            for (auto & p:chgq) {
                if (p.s > a.i) break;
                tmp[p.f.f] = p.f.s;
            }
            vector<int> ps;
            for (int x : dunno) {
                if (tmp[x] >= a.w) {
                    int A = find(v[x].a), B = find(v[x].b);
                    if (A!=B){
                        g[A].pb(B);
                        g[B].pb(A);
                        ps.pb(A); ps.pb(B);
                    }
                }
            }
            re = 0;
            DFS(find(a.s));
            ans[a.i] = re;
            for (int x : ps) {
                g[x].clear(); seen[x] = 0;
            }
            seen[find(a.s)] =0;
        }
//        sort(ALL(chgq), [&](pair<pii, int> a, pair<pii, int> b){return a.s < b.s;});
        for (auto & p : chgq) {
            v[p.f.f].w = p.f.s;
        }
    }
    for (int i = 0; i<q; ++i) {
        if (ans[i]) cout<<ans[i]<<endl;
    }
}

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