제출 #977703

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
977703		ZHIRDILBILDIZ	다리 (APIO19_bridges)	C++14	29 / 100	3072 ms	19764 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));
}

signed main () {
    // ios_base::sync_with_stdio(0);
    // cin.tie(0), cout.tie(0);

    int t = 1;
    // cin >> t;
    while (t--) {
        int n, m, q;
        cin >> n >> m;
        int u[m + 1], v[m + 1], w[m + 1];
        bool sub2 = 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;
        }
        while (q--) {
            int type;
            int l, r;
            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;
}

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