Submission #849549

#	Time	Username	Problem	Language	Result	Execution time	Memory
849549		hngwlog	Bridges (APIO19_bridges)	C++17	60 / 100	3049 ms	101640 KiB

bridges

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

#define fi first
#define se second
#define _size(x) (int)x.size()
#define BIT(i, x) ((x >> i) & 1)
#define MASK(n) ((1 << n) - 1)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define FOR(i, a, b) for (int i = a, _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = a, _b = (b); i >= _b; i--)
#define FORB1(i, mask) for (int i = mask; i > 0; i ^= i & - i)
#define FORB0(i, n, mask) for (int i = ((1 << n) - 1) ^ mask; i > 0; i ^= i & - i)
#define FORALL(i, a) for (auto i: a)
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);

struct edgeNode {

    int u, v, d;
};

struct queryNode {

    int type, b, r, s, w;
};

int n, m, q;
vector<edgeNode> edge;
vector<queryNode> qu;

bool checkSub1() {

    if (n <= 1000 && m <= 1000 && q <= 10000) return true;
    return false;
}

namespace subtask1 {

    int ans = 0;
    vector<int> vis;
    vector<vector<int>> adj;

    void dfs(int u, int w) {

        ans++;
        vis[u]++;
        FORALL(id, adj[u]) {
            int v = edge[id].u + edge[id].v - u;
            if (vis[v] || edge[id].d < w) continue;
            dfs(v, w);
        }
    }

    void main() {

        vis.resize(n + 1);
        adj.resize(n + 1);
        FOR(i, 1, m) adj[edge[i].u].push_back(i), adj[edge[i].v].push_back(i);
        REP(i, q) {
            if (qu[i].type == 1) edge[qu[i].b].d = qu[i].r;
            else {
                ans = 0;
                FOR(j, 1, n) vis[j] = 0;
                dfs(qu[i].w, qu[i].s);
                cout << ans << '\n';
            }
        }
    }
}

bool checkSub2() {

    if (m != n - 1) return false;
    FOR(i, 1, m) if (edge[i].u != i || edge[i].v != i + 1) return false;
    return true;
}

namespace subtask2 {

    const int inf = 1e9;

    struct segTree {

        vector<int> ST;

        void init(int n) {

            ST.resize(4 * n + 4);
        }

        void update(int id, int l, int r, int pos, int val) {

            if (pos < l || r < pos) return ;
            if (l == r) {
                ST[id] = val;
                return ;
            }
            int mid = (l + r) / 2;
            update(id * 2, l, mid, pos, val);
            update(id * 2 + 1, mid + 1, r, pos, val);
            ST[id] = min(ST[id * 2], ST[id * 2 + 1]);
        }

        int get(int id, int l, int r, int u, int v) {

            if (r < u || v < l) return inf;
            if (u <= l && r <= v) return ST[id];
            int mid = (l + r) / 2;
            return min(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
        }
    } st;

    void main() {

        st.init(n);
        FOR(i, 1, m) st.update(1, 1, n - 1, i, edge[i].d);
        REP(i, q) {
            if (qu[i].type == 1) st.update(1, 1, n - 1, qu[i].b, qu[i].r);
            else {
                int w = qu[i].w, s = qu[i].s;
                int k = 0;
                while ((1 << k) <= w - 1) k++;
                k--;
                int x = w;
                FORD(j, k, 0) if (x - (1 << j) > 0 && st.get(1, 1, n - 1, x - (1 << j), x - 1) >= s) x -= (1 << j);
                k = 0;
                while ((1 << k) <= n - 1 - w) k++;
                k--;
                FORD(j, k, 0) if (w + (1 << j) < n && st.get(1, 1, n - 1, w, w + (1 << j)) >= s) w += (1 << j);
                if (w == n || st.get(1, 1, n - 1, w, w) < s) w--;
                cout << w + 1 - x + 1 << '\n';
            }
        }
    }
}

bool checkSub4() {

    REP(i, q) if (qu[i].type == 1) return false;
    return true;
}

namespace subtask4 {

    vector<int> root, sz;

    int getroot(int u) {

        return root[u] == u ? u : (root[u] = getroot(root[u]));
    }

    bool unite(int u, int v) {

        u = getroot(u), v = getroot(v);
        if (u == v) return false;
        root[v] = u;
        sz[u] += sz[v];
        return true;
    }

    void main() {

        root.resize(n + 1), sz.resize(n + 1);
        FOR(i, 1, n) root[i] = i, sz[i] = 1;
        vector<pair<int, int>> cost;
        FOR(i, 1, m) cost.push_back({edge[i].d, i});
        sort(cost.begin(), cost.end(), [&] (const pair<int, int> a, pair<int, int> b) { return a.fi > b.fi; });
        vector<pair<int, int>> g;
        REP(i, q) g.push_back({qu[i].s, i});
        sort(g.begin(), g.end(), [&] (const pair<int, int> a, pair<int, int> b) { return a.fi > b.fi; });
        vector<int> ans(q);
        int j = 0;
        REP(i, q) {
            int id = g[i].se;
            while (j < _size(cost) && cost[j].fi >= g[i].fi) unite(edge[cost[j].se].u, edge[cost[j].se].v), j++;
            ans[id] = sz[getroot(qu[id].w)];
        }
        REP(i, q) cout << ans[i] << '\n';
    }
}

namespace fullsubtask {

    stack<int> _st;
    vector<int> root, sz;

    int getroot(int u) {

        return root[u] == u ? u : getroot(root[u]);
    }

    bool unite(int u, int v) {

        u = getroot(u), v = getroot(v);
        if (u == v) return false;
        _st.push(v);
        root[v] = u;
        sz[u] += sz[v];
        return true;
    }

    void main() {

    /***
        chia thanh sqrt(q) block queries
        voi moi block, update thi cap nhat trong so moi, calculation thi duyet lai cac canh changed
    */
        root.resize(n + 1);
        sz.resize(n + 1);
        int blockSz = 1000;
        int cnt = q / blockSz + (q % blockSz ? 1 : 0);
        vector<int> cntChange(m + 1), ans(q);
        vector<vector<int>> to_join(q);
        REP(l, cnt) {
            while (!_st.empty()) _st.pop();
            FOR(i, 1, n) root[i] = i, sz[i] = 1;
            FOR(i, 1, m) cntChange[i] = 0;
            int st = l * blockSz, en = min(q - 1, (l + 1) * blockSz - 1);
            vector<int> unchanged, changed, ask;
            FOR(i, st, en) {
                if (qu[i].type == 1) {
                    cntChange[qu[i].b]++;
                    changed.push_back(i);
                }
                else ask.push_back(i);
            }
            FOR(i, 1, m) if (!cntChange[i]) unchanged.push_back(i);
            FOR(i, st, en) {
                if (qu[i].type == 1) edge[qu[i].b].d = qu[i].r;
                else {
                    FORALL(id, changed) if (edge[qu[id].b].d >= qu[i].s) to_join[i].push_back(qu[id].b);
                }
            }
            sort(unchanged.begin(), unchanged.end(), [&] (const int i, int j) { return edge[i].d > edge[j].d; });
            sort(ask.begin(), ask.end(), [&] (const int i, int j) { return qu[i].s > qu[j].s; });
            int i = 0;
            FORALL(id, ask) {
                while (i < _size(unchanged) && edge[unchanged[i]].d >= qu[id].s) {
                    unite(edge[unchanged[i]].u, edge[unchanged[i]].v);
                    i++;
                }
                int _sz = _size(_st);
                FORALL(_id, to_join[id]) unite(edge[_id].u, edge[_id].v);
                ans[id] = sz[getroot(qu[id].w)];
                while (_size(_st) > _sz) {
                    int v = _st.top();
                    _st.pop();
                    sz[root[v]] -= sz[v];
                    root[v] = v;
                }
            }
        }
        REP(i, q) if (qu[i].type == 2) cout << ans[i] << '\n';
    }
}

int main() {
    fastio;

    cin >> n >> m;
    edge.resize(m + 1);
    FOR(i, 1, m) {
        int u, v, d;
        cin >> u >> v >> d;
        edge[i] = {u, v, d};
    }
    cin >> q;
    qu.resize(q);
    REP(i, q) {
        cin >> qu[i].type;
        if (qu[i].type == 1) cin >> qu[i].b >> qu[i].r;
        else cin >> qu[i].w >> qu[i].s;
    }
     if (checkSub1()) subtask1::main();
     else if (checkSub2()) subtask2::main();
     else if (checkSub4()) subtask4::main();
     else fullsubtask::main();
    return 0;
}

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