Submission #173136

#	Time	Username	Problem	Language	Result	Execution time	Memory
173136		TAISA_	Bridges (APIO19_bridges)	C++14	0 / 100	3042 ms	17564 KiB

bridges

#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
constexpr ll INF = (1LL << 30) - 1LL;
constexpr ll LINF = (1LL << 60) - 1LL;
constexpr ll MOD = 1e9 + 7;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }
int u[100000], v[100000], d[100000];
struct UnionFind {
    vector<int> par, siz;
    UnionFind(int n) {
        par.resize(n);
        siz.resize(n, 1);
        for (int i = 0; i < n; i++)
            par[i] = i;
    }
    int find(int x) {
        if (par[x] == x) {
            return x;
        } else {
            return par[x] = find(par[x]);
        }
    }
    bool unite(int u, int v) {
        u = find(u), v = find(v);
        if (u == v)
            return false;
        if (siz[u] < siz[v])
            swap(u, v);
        par[v] = u;
        siz[u] += siz[v];
        return true;
    }
    bool same(int u, int v) { return find(u) == find(v); }
};
vector<int> G[50000];
int ok[50000];
vector<int> vv;
void dfs(int i) {
    ok[i] = 1;
    vv.emplace_back(i);
    for (auto &e : G[i]) {
        if (ok[e]) {
            continue;
        }
        dfs(e);
    }
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    const int b = 1000;
    int n, m;
    cin >> n >> m;
    set<pair<P, P>, greater<pair<P, P>>> es;
    for (int i = 0; i < m; i++) {
        cin >> u[i] >> v[i] >> d[i];
        --u[i];
        --v[i];
        es.insert(make_pair(P(d[i], i), P(u[i], v[i])));
    }
    int q;
    cin >> q;
    vector<int> t(q), s(q), w(q), vis(m), res(q, -1);
    vector<pair<P, int>> qs;
    for (int i = 0; i < q; i++) {
        cin >> t[i] >> s[i] >> w[i];
        --s[i];
        if (t[i] == 1) {
            vis[s[i]] = 1;
        } else {
            qs.emplace_back(make_pair(P(w[i], s[i]), i));
        }
        if (i % b < b - 1 && i != q - 1) {
            continue;
        }
        sort(all(qs));
        reverse(all(qs));
        UnionFind uf(n);
        int fs = (i / b) * b;
        auto it = es.begin();
        for (int j = 0; j < qs.size(); j++) {
            int ww = qs[j].first.first, st = qs[j].first.second,
                idx = qs[j].second;
            while (it != es.end() && (*it).first.first >= ww) {
                if (!vis[(*it).first.second]) {
                    uf.unite((*it).second.first, (*it).second.second);
                }
                it++;
            }
            vector<int> nv;
            for (int k = fs; k <= i; k++) {
                if (t[k] == 1) {
                    if ((k < idx && w[k] >= ww) || (k > idx && d[s[k]] >= ww)) {
                        nv.emplace_back(uf.find(u[s[k]]));
                        nv.emplace_back(uf.find(v[s[k]]));
                    }
                }
            }
            sort(all(nv));
            nv.erase(unique(all(nv)), nv.end());
            for (int k = fs; k <= i; k++) {
                if (t[k] == 1) {
                    if ((k < idx && w[k] >= ww) || (k > idx && d[s[k]] >= ww)) {
                        G[uf.find(u[s[k]])].emplace_back(uf.find(v[s[k]]));
                        G[uf.find(v[s[k]])].emplace_back(uf.find(u[s[k]]));
                    }
                }
            }
            dfs(uf.find(st));
            res[idx] = 0;
            for (auto &e : vv) {
                res[idx] += uf.siz[uf.find(e)];
                ok[uf.find(e)] = 0;
            }
            for (auto &e : nv) {
                G[e].clear();
            }
            vv.clear();
        }
        vis.assign(m, 0);
        for (int j = fs; j <= i; j++) {
            if (t[j] == 1) {
                es.erase(make_pair(P(d[s[j]], s[j]), P(u[s[j]], v[s[j]])));
                d[s[j]] = w[j];
                es.insert(make_pair(P(d[s[j]], s[j]), P(u[s[j]], v[s[j]])));
            }
        }
    }
    for (int i = 0; i < q; i++) {
        if (res[i] != -1) {
            cout << res[i] << endl;
        }
    }
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:85:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < qs.size(); j++) {
                         ~~^~~~~~~~~~~

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