Submission #1117244

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117244		Mike_Vu	Bridges (APIO19_bridges)	C++14	100 / 100	1438 ms	11420 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(x) (1LL<<(x))
#define BITj(x, j) (((x)>>(j))&1)
#define ALL(v) (v).begin(), (v).end()

template<typename T> bool maximize(T &x, const T &y) {
    if (x < y) {x = y; return 1;}
    return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
    if (x > y) {x = y; return 1;}
    return 0;
}

struct DSU{
    int n;
    vector<int> dsu;
    void init(int _n = 0) {
        n = _n;
        dsu.assign(n+1, -1);
    }
    int f(int u) {
        return dsu[u] < 0 ? u : dsu[u] = f(dsu[u]);
    }
    int sz(int u) {
        return -dsu[f(u)];
    }
    bool join(int u, int v) {
        u = f(u);
        v = f(v);
        if (u == v) return 0;
        if (dsu[u] > dsu[v]) swap(u, v);
        dsu[u] += dsu[v];
        dsu[v] = u;
        return 1;
    }
};

struct query{
    int u, w, ans;
    bool type;
    query(bool _type, int _u, int _w) {
        type = _type;
        u = _u;
        w = _w;
    }
};

const int maxn = 5e4+5, maxm = 1e5+5, B = 500;///B = 200
int n, m, q;
vector<pii> edges; ///edges
vector<int> curw; ///current weight
vector<query> qu;
DSU dsu;

namespace sub1{
    bool check() {
        return (min(n, m) <= 1005 && q <= 10005);
    }
    void solve() {
        //for every query -> build dsu from scratch
        for (int i = 0; i < q; i++) {
            if (qu[i].type == 0) {
                //update
                curw[qu[i].u] = qu[i].w;

            }
            else {
                dsu.init(n);
                for (int id = 0; id < m; id++) {
                    if (curw[id] >= qu[i].w) {
                        dsu.join(edges[id].fi, edges[id].se);
                    }
                }
                cout << dsu.sz(qu[i].u) << "\n";
            }
        }
    }
}

namespace sub6{
    bool cmpedgeid1(const int &a, const int &b) {
        if (curw[a] != curw[b]) return curw[a] > curw[b];
        return a < b;
    }
    bool cmpqub(pii a, pii b){
        if (qu[a.fi].w != qu[b.fi].w) return qu[a.fi].w > qu[b.fi].w;
        return a.se < b.se;
    }
    multiset<int, bool (*) (const int &, const int &)> st(cmpedgeid1);
    vector<int> adj[maxn], curup, tempw, curedges;
    vector<pii> curqu;
    bool vis[maxn];
    int curans;
    void dfs(int u) {
        vis[u] = 1;
        curans += dsu.sz(u);
        for (int v : adj[u]) {
            if (!vis[v]) {
                dfs(v);
            }
        }
    }
    void solveblock(int ql, int qr) {
        //remove edges inside this block in set
        int sumt = 0;
        for (int i = ql; i <= qr; i++) {
            if (qu[i].type == 0) {
                //update
                int u = qu[i].u;
                auto it = st.find(u);
                if (it != st.end()) st.erase(it);
                curup.pb(i);
                curedges.pb(u);
                ++sumt;
            }
            else {
                curqu.pb({i, sumt});
            }
        }
        //discretize edges
        sort(ALL(curedges));
        curedges.erase(unique(ALL(curedges)), curedges.end());
        //check for weights
        //sort nodes' weights descendingly
        sort(ALL(curqu), cmpqub);
        dsu.init(n);
        auto allit = st.begin();
        //for each query
        for (pii e : curqu) {
            int quid = e.fi, start = qu[quid].u, bound = qu[quid].w, curt = e.se;
//            cout << quid << ' ' << curt << "\n";
            //DSU
            while (allit != st.end() && curw[(*allit)] >= bound) {
                dsu.join(edges[(*allit)].fi, edges[(*allit)].se);
                ++allit;
            }
            //update weight
            for (int t = 0; t < curt; t++) {
                int id = curup[t];
                tempw[qu[id].u] = qu[id].w;
            }
            //build graph
            for (int id : curedges){
                if (tempw[id] < bound) continue;
                int u = edges[id].fi, v = edges[id].se;
                u = dsu.f(u);
                v = dsu.f(v);
                if (u == v) continue;
                adj[u].pb(v);
                adj[v].pb(u);
            }
            //dfs count
            curans = 0;
            int startreal = dsu.f(start);
            dfs(startreal);
            qu[quid].ans = curans;
            //clear adj, tempw, vis
            vis[startreal] = 0;
            for (int id : curedges){
                tempw[id] = curw[id];
                int u = edges[id].fi, v = edges[id].se;
                u = dsu.f(u);
                v = dsu.f(v);
                if (u == v) continue;
                adj[u].clear();
                adj[v].clear();
                vis[u] = vis[v] = 0;
            }
        }
        //after this block -> update set, curw
        for (int id : curup) {
            curw[qu[id].u] = qu[id].w;
        }
        //set
        for (int id : curedges) {
            tempw[id] = curw[id];
            st.insert(id);
        }
        //clear
        curup.clear();
        curedges.clear();
        curqu.clear();
    }
    void solve() {
        //prepare list of edges in descending order -> set
        //init part
        for (int i = 0; i < m; i++) {
            st.insert(i);
            tempw.pb(curw[i]); //save the temp weight -> undo
        }
        memset(vis, 0, sizeof(vis));
        //for every B queries
        for (int numb = 0; numb*B < q; numb++) {
            solveblock(numb*B, min(numb*B+B-1, q-1));
        }
        //output
        for (int i = 0; i < q; i++) {
            if (qu[i].type) {
                cout << qu[i].ans << "\n";
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    #define name "task"
//    if (fopen(name".inp", "r")) {
//        freopen(name".inp", "r", stdin);
//        freopen(name".out", "w", stdout);
//    }
    //input
    cin >> n >> m;
    for (int i= 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges.pb({u, v});
        curw.pb(w);
    }
    cin >> q;
    for (int i = 0; i < q; i++) {
        int t, u, w;
        cin >> t >> u >> w;
        qu.pb(query(t==2, t == 1 ? u-1 : u, w));
    }
//    if (sub1::check()) return sub1::solve(), 0;
    return sub6::solve(), 0;
}
/*
5 1
4 5 1
3
1 1 13
2 5 13
2 5 4

5 1
4 5 1
5
1 1 13
2 5 13
2 5 4
2 1 13
2 3 3
2
2
1
1

3 4
1 2 5
2 3 2
3 1 4
2 3 8
5
2 1 5
1 4 1
2 2 5
1 1 1
2 3 2

7 8
1 2 5
1 6 5
2 3 5
2 7 5
3 4 5
4 5 5
5 6 5
6 7 5
12
2 1 6
1 1 1
2 1 2
1 2 3
2 2 2
1 5 2
1 3 1
2 2 4
2 4 2
1 8 1
2 1 1
2 1 3
*/

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