Submission #1110610

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110610		_callmelucian	Bridges (APIO19_bridges)	C++14	100 / 100	1466 ms	26312 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpl;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 2e5 + 5;
const int srt = 316;

struct qItem {
    int type, s, w, idx;

    qItem() : type(0), s(0), w(0), idx(0) {}
    qItem (int type, int s, int w, int idx) : type(type), s(s), w(w), idx(idx) {}

    bool operator < (const qItem &o) const {
        if (idx / srt == o.idx / srt) {
            if (type == o.type) return (type == 2 ? w > o.w : idx < o.idx);
            return type < o.type;
        }
        return idx / srt < o.idx / srt;

    }
};

struct DSU {
    vector<int> lab;
    DSU (int sz) : lab(sz + 1, -1) {}

    int get (int u) {
        if (lab[u] < 0) return u;
        return lab[u] = get(lab[u]);
    }

    void unite (int a, int b) {
        a = get(a), b = get(b);
        if (a == b) return;
        if (-lab[a] < -lab[b]) swap(a, b);
        lab[a] += lab[b], lab[b] = a;
    }

    int getSize (int u) { return -lab[get(u)]; }
};

vector<int> helper[mn], adj[mn], weightClass, staticEdge, dynamicEdge, visList;
int u[mn], v[mn], weight[mn], ans[mn], wClass[mn];
bool vis[mn];

void dfs (int u, int id, DSU &dsu) {
    ans[id] += dsu.getSize(u), vis[u] = 1;
    visList.push_back(u);
    for (int v : adj[u])
        if (!vis[v]) dfs(v, id, dsu);
}

int getClass (int w) {
    return lower_bound(all(weightClass), w) - weightClass.begin();
}

void sortEdge() {
    for (int u : staticEdge)
        helper[wClass[u]].push_back(u);
    staticEdge.clear();

    for (int i = (int)weightClass.size() - 1; i >= 0; i--) {
        for (int u : helper[i]) staticEdge.push_back(u);
        helper[i].clear();
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    /// read input and compress edges
    int n, m; cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> u[i] >> v[i] >> weight[i];
        weightClass.push_back(weight[i]);
    }

    int q; cin >> q;
    vector<qItem> queries(q);
    for (int i = 0; i < q; i++) {
        int type, s, w; cin >> type >> s >> w;
        queries[i] = qItem(type, s, w, i);
        if (type == 1)
            weightClass.push_back(w);
    }
    sort(all(queries));
    sort(all(weightClass)), filter(weightClass);

    for (int i = 1; i <= m; i++)
        wClass[i] = getClass(weight[i]);

    /// process queries by blocks
    for (int startRound = 0; startRound < q; startRound += srt) {
        int L = startRound, R = min(q - 1, startRound + srt - 1), iter = 0;

        // setup static edges
        vector<bool> isStatic(m + 1, 1);
        for (int i = L; i <= R; i++)
            if (queries[i].type == 1) isStatic[queries[i].s] = 0;
        staticEdge.clear(), dynamicEdge.clear();
        for (int i = 1; i <= m; i++) {
            if (isStatic[i]) staticEdge.push_back(i);
            else dynamicEdge.push_back(i);
        }
        sortEdge();

        // process queries within blocks
        DSU dsu(n);
        for (int i = L; i <= R; i++) {
            if (queries[i].type == 1) continue;

            // add static edges
            while (iter < staticEdge.size() && weight[staticEdge[iter]] >= queries[i].w) {
                int e = staticEdge[iter++];
                dsu.unite(u[e], v[e]);
            }

            // add dynamic edges
            vector<int> saveNode;
            function<void(int,int)> addEdge = [&] (int a, int b) {
                a = dsu.get(a), b = dsu.get(b);
                if (a == b) return;
                adj[a].push_back(b), saveNode.push_back(a);
                adj[b].push_back(a), saveNode.push_back(b);
            };
            for (int j = R; j >= L; j--) {
                if (queries[j].idx >= queries[i].idx || queries[j].type == 2 || isStatic[queries[j].s]) continue;
                int e = queries[j].s, w = queries[j].w;
                isStatic[e] = 1; // just reusing memory
                if (w >= queries[i].w) addEdge(u[e], v[e]);
            }
            for (int e : dynamicEdge) {
                if (isStatic[e]) continue;
                if (weight[e] >= queries[i].w) addEdge(u[e], v[e]);
            }

            // run dfs
            dfs(dsu.get(queries[i].s), queries[i].idx, dsu);

            // remove dynamic edges & refresh vis array
            for (int u : saveNode) adj[u].clear();
            for (int u : visList) vis[u] = 0;
            for (int u : dynamicEdge) isStatic[u] = 0;
            visList.clear();
        }

        // update edges' weight
        for (int i = L; i <= R; i++) {
            if (queries[i].type == 2) continue;
            int e = queries[i].s, w = queries[i].w;
            weight[e] = w, wClass[e] = getClass(w);
        }
    }

    /// print answer for queries
    for (int i = 0; i < q; i++)
        if (ans[i]) cout << ans[i] << "\n";

    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:124:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |             while (iter < staticEdge.size() && weight[staticEdge[iter]] >= queries[i].w) {
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~

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