Submission #1062461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062461		manhlinh1501	Bridges (APIO19_bridges)	C++17	13 / 100	215 ms	7788 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using pii = pair<int, int>;
const int MAXN = 1e5 + 5;

struct event {
    int type, x, y;
    event(int type = 0, int x = 0, int y = 0 ): type(type), x(x), y(y) {}
};

struct edge {
    int u, v, w;
    edge(int u = 0, int v = 0, int w = 0) : u(u), v(v), w(w) {}
};

int N, M, Q;
edge e[MAXN];
event query[MAXN];

namespace subtask1 {
    const int MAXN = 1e3 + 5;

    vector<pii> adj[MAXN];
    bool vis[MAXN];

    bool is_subtask() {
        return N <= MAXN and M <= MAXN;
    }

    int DFS(int u, int x) {
        vis[u] = true;
        int res = 1;
        for(auto [v, w] : adj[u]) {
            if(vis[v] == false and w >= x)
                res += DFS(v, x);
        }
        return res;
    }

    int calc(int x, int y) {
        for(int i = 1; i <= N; i++) {
            vis[i] = false;
            adj[i].clear();
        }

        for(int i = 1; i <= M; i++) {
            auto [u, v, w] = e[i];
            adj[u].emplace_back(v, w);
            adj[v].emplace_back(u, w);
        }

        return DFS(x, y);
    }

    void solution() {
        if(is_subtask() == false) return;
        for(int i = 1; i <= Q; i++) {
            auto [type, x, y] = query[i];
            if(type == 1) {
                e[x].w = y;
            } else {
                cout << calc(x, y) << "\n";
            }
        }
        exit(0);
    }
}

namespace subtask2 {
    bool is_subtask() {
        for(int i = 1; i <= M; i++) {
            auto [u, v, w] = e[i];
            if(u == i and v == i + 1)
                continue;
            else return false;
        }
        return N - 1 == M;
    }

    struct segment_tree {
        int N;
        int tree[MAXN * 4];

        void init(int _N) {
            N = _N;
        }

        void update(int p, int x) {
            int l = 1, r = N, id = 1;
            while(l < r) {
                int m = (l + r) / 2;
                if(p <= m) {
                    id = id * 2;
                    r = m;
                } else {
                    id = id * 2 + 1;
                    l = m + 1;
                }
            }
            tree[id] = x;
            while(id >= 1) {
                id >>= 1;
                tree[id] = max(tree[id * 2], tree[id * 2 + 1]);
            }
        }

        int get(int id, int l, int r, int u, int v) {
            if(r < u or l > v) return 0;
            if(u <= l and r <= v) return tree[id];
            int m = (l + r) / 2;
            return min(get(id * 2, l, m, u, v), get(id * 2 + 1, m + 1, r, u, v));
        }

        int get(int l, int r) {
            return get(1, 1, N, l, r);
        }
    } ST;

    void solution() {
        if(is_subtask() == false) return;
        ST.init(N);
        for(int i = 1; i <= M; i++) {
            auto [u, v, w] = e[i];
            ST.update(u, w);
        }
        for(int i = 1; i <= Q; i++) {
            auto [type, x, y] = query[i];
            if(type == 1) {
                ST.update(x, y);
            } else {
                int ans = 0;

                {
                    int low = x, high = N, p = -1;
                    while(low <= high) {
                        int mid = (low + high) / 2;
                        if(ST.get(x, mid) >= y) {
                            p = mid;
                            low = mid + 1;
                        } else high = mid - 1;
                    }
                    if(p != -1) ans += (p - x + 1);
                }

                {
                    int low = 1, high = x, p = -1;
                    while(low <= high) {
                        int mid = (low + high) / 2;
                        if(ST.get(mid, x) >= y) {
                            p = mid;
                            high = mid - 1;
                        } else low = mid + 1;
                    }
                    if(p != -1) ans += (x - p + 1);
                }
                cout << ans << "\n";
            }
        }
        exit(0);
    }
}

signed main() {
#define TASK "code"

    if (fopen(TASK ".inp", "r")) {
        freopen(TASK ".inp", "r", stdin);
        freopen(TASK ".out", "w", stdout);
    }

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;

    for(int i = 1; i <= M; i++) {
        auto &[u, v, w] = e[i];
        cin >> u >> v >> w;
    }

    cin >> Q;
    for(int i = 1; i <= Q; i++) {
        auto &[type, x, y] = query[i];
        cin >> type >> x >> y;
    }
    subtask1::solution();
    subtask2::solution();
    return (0 ^ 0);
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:168:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  168 |         freopen(TASK ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:169:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |         freopen(TASK ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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