Submission #848583

#	Time	Username	Problem	Language	Result	Execution time	Memory
848583		hngwlog	Bridges (APIO19_bridges)	C++14	43 / 100	441 ms	10120 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 checkSub3() {

    if (m != n - 1) return false;
    int res = 1, ok = 0;
    FOR(i, 1, 15) {
        res *= 2;
        if (n == res - 1) ok++;
    }
    if (!ok) return false;
    FOR(i, 1, m) if (edge[i].u != (i + 1) / 2 || edge[i].v != i + 1) return false;
    return true;
}

namespace subtask3 {

    void main() {


    }
}

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';
    }
}

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 (checkSub3()) subtask3::main();
    else if (checkSub4()) subtask4::main();
    return 0;
}

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