Submission #477979

#	Time	Username	Problem	Language	Result	Execution time	Memory
477979		jeroenodb	Bridges (APIO19_bridges)	C++14	100 / 100	2538 ms	12896 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> szpar;
    int components;
    DSU(int n) {
        szpar.assign(n+1,-1);
        components = n;
    }
    void reset() {
        fill(all(szpar),-1);
        components=szpar.size()-1;
    }
    void link(int a, int b) {
        components--;
        if(szpar[a]>szpar[b]) {
            swap(a,b);
        }
        szpar[a] += szpar[b];
        szpar[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) {
        if(szpar[a]<0) return a;
        return szpar[a] = find(szpar[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) const {
        return w>o.w;
    }
};
const int B=807;
struct query {
    int t,b,r;
};
edge es[mxN];
struct comp{ bool operator()(int a, int b) const {return es[a]<es[b] or (es[a].w==es[b].w and a<b);} };
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m; cin >> n >> m;
    for(int i=0;i<m;++i) {
        auto& e = es[i];
        cin >> e.a >> e.b >> e.w;
        e.a--,e.b--;
    }
    int Q; cin >> Q;
    
    set<int,comp> order;
    for(int i=0;i<m;++i) order.insert(i);
    DSU dsu(n),dsu2(n);
    mys s,s2,verts;
    vvi adj(n);
    vector<query> qs;
    for(int iter=0;iter<Q;iter+=B) {
        int len = min(B,Q-iter);
        qs.resize(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; rq.reserve(len);
        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;});
        dsu.reset();
        auto it = rq.begin();
        auto it2 = order.begin();
        while(it!=rq.end()) {
            if(it2==order.end() or (it!=rq.end() and qs[*it].r>es[*it2].w)) {
                // do query
                auto add= [&](int a, int b) {
                    a=dsu.find(a), b=dsu.find(b);
                    if(!verts.add(a)) adj[a].clear();
                    if(!verts.add(b)) adj[b].clear();
                    if(a==b) return;
                    adj[a].push_back(b);
                    adj[b].push_back(a);
                };
                s2.reset();
                verts.reset();
                auto& q = qs[*it];
                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) add(e.a,e.b);
                    }
                }
                
                for(auto i:s.st) {
                    if(!s2.vis[i]) {
                        auto& e = es[i];
                        if(e.w>=q.r) add(e.a,e.b);
                    }
                }
                int mycomp = dsu.find(q.b);
                vi st; st.push_back(mycomp);
                add(mycomp,mycomp);
                verts.reset();
                verts.add(mycomp);
                q.b=0;
                while(!st.empty()) {
                    int at = st.back(); st.pop_back();
                    q.b+=-dsu.szpar[at];
                    for(int to : adj[at]) if(!verts.vis[to]) {
                        verts.add(to);
                        st.push_back(to);
                    }
                }
                ++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) {
                order.erase(q.b);
                es[q.b].w = q.r;
                order.insert(q.b);
            } 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: 27 / 27