Submission #977725

#	Time	Username	Problem	Language	Result	Execution time	Memory
977725		ZHIRDILBILDIZ	Bridges (APIO19_bridges)	C++14	43 / 100	692 ms	27092 KiB

bridges

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>

using namespace std;
const int N = (1 << 16);

set<pair<pii, int>> gr[N];
bool us[N];
vector<int> now;
void dfs (int city, int w) {
    us[city] = 1;
    now.push_back(city);
    for (auto i : gr[city]) {
        if (us[i.fi.fi] || i.fi.se < w)
            continue;
        dfs(i.fi.fi, w);
    }
}
int mn[2 * N + 1];
void update (int l, int r, int ind, int x, int v) {
    if (l > ind || r < ind)
        return;
    if (l == r) {
        mn[v] = x;
        return;
    }
    int mid=(l + r) >> 1;
    update(l, mid, ind, x, v << 1);
    update(mid + 1, r, ind, x, v << 1 ^ 1);
    mn[v] = min(mn[v << 1], mn[v << 1 ^ 1]);
}
int get_min (int l, int r, int l1, int r1, int v) {
    if (l > r1 || r < l1)
        return 1e9;
    if (l1 <= l && r <= r1)
        return mn[v];
    int mid = (l + r) >> 1;
    return min(get_min(l, mid, l1, r1, v << 1), get_min(mid + 1, r, l1, r1, v << 1 ^ 1));
}

int p[N];
int sz[N];
void init (int _sz) {
    for (int i = 1; i <= _sz; ++i)
        p[i] = i,
            sz[i] = 1;
}
int get (int u) {
    if (u != p[u])
        p[u] = get(p[u]);
    return p[u];
}
void join (int u, int v) {
    u = get(u);
    v = get(v);
    if (u == v)
        return;
    if (sz[u] > sz[v])
        swap(u, v);
    sz[v] += sz[u];
    p[u] = v;
    sz[u] = 0;
}
signed main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int t = 1;
    while (t--) {
        int n, m, q;
        cin >> n >> m;
        int u[m + 1], v[m + 1], w[m + 1];

        bool sub2 = 1;
        bool sub4 = 1;

        for (int i = 1; i <= m; ++i) {
            cin >> u[i] >> v[i] >> w[i];
            if (u[i] != i && v[i] != i + 1)
                sub2 = 0;
            gr[u[i]].insert({{v[i], w[i]}, i});
            gr[v[i]].insert({{u[i], w[i]}, i});
        }
        cin >> q;

        if (sub2 && m == n - 1) {
            for (int i = 1; i < n; ++i)
                update(1, N, i, w[i], 1);
            while (q--) {
                int type, l, r;
                cin >> type >> l >> r;
                if (type == 1) {
                    update(1, N, l, r, 1);
                    continue;
                }
                int l1 = 0, r1 = l;
                while (l1 + 1 < r1) {
                    int mid = (l1 + r1) >> 1;
                    if (get_min(1, N, mid, l - 1, 1) >= r)
                        r1 = mid;
                    else
                        l1 = mid;
                }
                int l2 = l - 1, r2 = n;
                while (l2 + 1 < r2) {
                    int mid = (l2 + r2) >> 1;
                    if (get_min(1, N, l, mid, 1) >= r)
                        l2 = mid;
                    else
                        r2 = mid;
                }
                cout << l - r1 + (l2 - l + 1) + 1 << '\n';
            }
            continue;
        }

        int qtype[q + 1], ql[q + 1], qr[q + 1];
        for (int i = 1; i <= q; ++i) {
            cin >> qtype[i] >> ql[i] >> qr[i];
            if (qtype[i] == 1)
                sub4 = 0;
        }

        if (sub4) {
            init(n);

            vector<pair<pii, int>> query;
            vector<pair<int, pii>> road;
            int ans[q + 1] = {};

            for (int i = 1; i <= m; ++i)
                road.push_back({w[i], {u[i], v[i]}});
            for (int i = 1; i <= q; ++i)
                query.push_back({{qr[i], ql[i]}, i});

            sort(road.begin(), road.end());
            sort(query.begin(), query.end());

            reverse(road.begin(), road.end());
            reverse(query.begin(), query.end());

            int uk = 0;
            for (int i = 0; i < q; ++i) {
                auto p = query[i];
                while (uk < road.size() && road[uk].fi >= p.fi.fi) {
                    join(road[uk].se.fi, road[uk].se.se);
                    // cout << "join " << road[uk].se.fi << " with " << road[uk].se.se << '\n';
                    ++uk;
                }
                // cout << "answer, p.fi.se = " << sz[get(p.fi.se)] << ' ' << p.fi.se << '\n';
                ans[p.se] = sz[get(p.fi.se)];
            }

            for (int i = 1; i <= q; ++i)
                cout << ans[i] << ' ';
            cout << '\n';

            continue;
        }

        for (int i = 1; i <= q; ++i) {
            int type = qtype[i];
            int l = ql[i], r = qr[i];
            // cin >> type >> l >> r;
            if (type == 1) {
                gr[u[l]].erase({{v[l], w[l]}, l});
                gr[v[l]].erase({{u[l], w[l]}, l});
                w[l] = r;
                gr[u[l]].insert({{v[l], w[l]}, l});
                gr[v[l]].insert({{u[l], w[l]}, l});
            } else {
                now.clear();
                dfs(l, r);
                for (int i : now)
                    us[i] = 0;
                cout << now.size() << '\n';
            }
        }
    }

    return 0;
}

// 7 8
// 1 2 200
// 1 5 100
// 2 5 30
// 5 3 25
// 5 4 17
// 4 3 9
// 3 6 11
// 3 7 12
// 5
// 2 3 25
// 2 3 10
// 2 1 100
// 2 1 200
// 2 5 15

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:149:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |                 while (uk < road.size() && road[uk].fi >= p.fi.fi) {
      |                        ~~~^~~~~~~~~~~~~

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