Submission #823976

#	Time	Username	Problem	Language	Result	Execution time	Memory
823976		hngwlog	Bridges (APIO19_bridges)	C++14	13 / 100	274 ms	7240 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 (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 (st.get(1, 1, n, w, w + (1 << j)) >= s) w += (1 << j);
                cout << w + 1 - x + 1 << '\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();

    return 0;
}

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