Submission #636545

#	Time	Username	Problem	Language	Result	Execution time	Memory
636545		MohamedFaresNebili	Bridges (APIO19_bridges)	C++14	0 / 100	498 ms	524288 KiB

bridges

#include <bits/stdc++.h>

            using namespace std;

            const int INF = INT32_MAX;
            const int LOG = 17;

            int N, M, Q, par[50005], dep[50005];
            int timer, tin[200005], out[200005];
            int lazy[200005], ST[200005];
            vector<array<int, 2>> E;
            vector<pair<int, int>> adj[50005];

            void prop(int v, int l, int r) {
                if(l == r) return;
                lazy[v * 2] = min(lazy[v * 2], lazy[v]);
                ST[v * 2] = min(ST[v * 2], lazy[v]);

                lazy[v * 2 + 1] = min(lazy[v * 2 + 1], lazy[v]);
                ST[v * 2 + 1] = min(ST[v * 2 + 1], lazy[v]);
                lazy[v] = INF;
            }
            void update(int v, int l, int r, int lo, int hi, int val) {
                prop(v, l, r);
                if(l > hi || r < lo) return;
                if(l >= lo && r <= hi) {
                    ST[v] = min(ST[v], val); lazy[v] = min(lazy[v], val);
                    prop(v, l, r);
                    return;
                }
                update(v * 2, l, (l + r) / 2, lo, hi, val);
                update(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, val);
                ST[v] = min(ST[v * 2], ST[v * 2 + 1]);
            }
            int query(int v, int l, int r, int lo, int hi, int val) {
                prop(v, l, r);
                if(l > hi || r < lo || ST[v] < val) return 0;
                if(ST[v] >= val) return max(0, max(l, lo) - min(r, hi) + 1);
                return query(v * 2, l, (l + r) / 2, lo, hi, val) +
                    query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, val);
            }
            void dfs(int v, int p) {
                par[v] = p; tin[v] = ++timer;
                for(auto u : adj[v]) {
                    if(u.first == p) continue;
                    dep[u.first] = u.second; dfs(u.first, v);
                }
                out[v] = timer; update(1, 1, N, tin[v] + 1, out[v], dep[v]);
            }

            int32_t main() {
                ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                cin >> N >> M;
                for(int l = 0; l < M; l++) {
                    int U, V, D; cin >> U >> V >> D;
                    if(U > V) swap(U, V); E.push_back({U, V});
                    adj[U].push_back({V, D});
                    adj[V].push_back({U, D});
                }
                dep[1] = INF; dfs(1, 1); cin >> Q;
                while(Q--) {
                    int t; cin >> t;
                    if(t == 1) {
                        int B, R; cin >> B >> R; --B;
                        int U = E[B][0], V = E[B][1];
                        update(1, 1, N, tin[V] + 1, out[V], R);
                    }
                    if(t == 2) {
                        int S, W; cin >> S >> W;
                        while(S != 1 && dep[S] >= W) S = par[S];
                        cout << 1 + query(1, 1, N, tin[S] + 1, out[S], W) << "\n";
                    }
                }
                return 0;
            }

Compilation message (stderr)

bridges.cpp: In function 'int32_t main()':
bridges.cpp:56:21: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   56 |                     if(U > V) swap(U, V); E.push_back({U, V});
      |                     ^~
bridges.cpp:56:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   56 |                     if(U > V) swap(U, V); E.push_back({U, V});
      |                                           ^
bridges.cpp:65:29: warning: unused variable 'U' [-Wunused-variable]
   65 |                         int U = E[B][0], V = E[B][1];
      |                             ^

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