Submission #477892

#	Time	Username	Problem	Language	Result	Execution time	Memory
477892		jeroenodb	Bridges (APIO19_bridges)	C++14	73 / 100	3071 ms	6536 KiB

bridges

#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
struct DSU{
    vector<int> sz,parent;
    int components;
    struct update {
        int a,b,sz;
    };
    vector<update> st;
    stack<int> checkpoint;
    DSU(int n) {
        sz.assign(n+1,1);
        components = n;
        parent.resize(n+1);
        for(int i=1;i<=n;++i) parent[i]=i;
    }
    void tocheck() {
        while(components!=checkpoint.top()) {
            rollback();
        }
        checkpoint.pop();
    }
    void reset() {
        st.clear();
        fill(all(sz),1);
        iota(all(parent),0);
        components=parent.size()-1;
    }
    void rollback() {
        components++;
        update l = st.back();
        st.pop_back();
        sz[l.a] = l.sz;
        parent[l.b] = l.b;
    }
    void link(int a, int b) {
        components--;
        if(sz[a]<sz[b]) {
            swap(a,b);
        }
        if(!checkpoint.empty()) st.push_back({a,b,sz[a]});
        sz[a] +=sz[b];
        parent[b] = a;
    }
    void unite(int a, int b) {
        int pa = find(a),pb = find(b);
        if(pa!=pb) {
            link(pa,pb);
        }
    }
    int find(int a) {
        while(parent[a]!=a) {
            a = parent[a];
        }
        return a;
    }
};
struct mys {
    bitset<mxN> vis;
    vi st;
    bool add(int i) {
        if(vis[i]) return true;
        vis[i]=true;
        st.push_back(i);
        return false;
    }
    void reset() {
        for(auto i : st) vis[i]=false;
        st.clear();
    }
};
struct edge{ 
    int a,b,w;
    bool operator<(const edge& o) {
        return w>o.w;
    }
};
const int B=360;
struct query {
    int t,b,r;
};
int main() {
    int n,m; cin >> n >> m;
    vector<edge> es(m);
    for(auto& e : es) {
        cin >> e.a >> e.b >> e.w;
        e.a--,e.b--;
    }
    int Q; cin >> Q;
    vi order(m);
    iota(all(order),0);
    DSU dsu(n);
    mys s,s2;
    for(int iter=0;iter<Q;iter+=B) {
        int len = min(B,Q-iter);
        vector<query> qs(len);
        s.reset();
        for(auto& q : qs) {
            cin >> q.t >> q.b >> q.r;
            q.b--;
            if(q.t==1) {
                s.add(q.b);
            }
        }

        vi rq;
        for(int i=0;i<len;++i) if(qs[i].t==2) rq.push_back(i);
        sort(all(rq), [&](int c,int d){return qs[c].r>qs[d].r;});
        sort(all(order),[&](int c,int d){return es[c]<es[d];});
        dsu.reset();
        auto it = rq.begin(), it2 = order.begin();
        while(it!=rq.end() or it2!=order.end()) {
            if(it2==order.end() or (it!=rq.end() and qs[*it].r>es[*it2].w)) {
                // do query
                s2.reset();
                auto& q = qs[*it];
                dsu.checkpoint.push(dsu.components);
                for(int j=*it-1;j>=0;--j) {
                    if(qs[j].t==1 and !s2.vis[qs[j].b]) {
                        s2.add(qs[j].b);
                        auto& e = es[qs[j].b];
                        if(qs[j].r>=q.r) dsu.unite(e.a,e.b);
                    }
                }
                for(auto i:s.st) {
                    if(!s2.vis[i]) {
                        auto& e = es[i];
                        if(e.w>=q.r) dsu.unite(e.a,e.b);
                    }
                }
                q.b=dsu.sz[dsu.find(q.b)];
                dsu.tocheck();
                ++it;
            } else {
                auto& e = es[*it2];
                if(!s.vis[*it2]) dsu.unite(e.a,e.b);
                ++it2;
            }
        }
        for(auto& q : qs) {
            if(q.t==1) {
                es[q.b].w = q.r;
            } else {
                cout << q.b << '\n';
            }
        }
    }
}

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