Submission #636612

#	Time	Username	Problem	Language	Result	Execution time	Memory
636612		MohamedFaresNebili	Bridges (APIO19_bridges)	C++14	100 / 100	2193 ms	31100 KiB

bridges

#include <bits/stdc++.h>

            using namespace std;

            const int batch = 1001;

            int N, M, Q, ans[100001];;
            int S[100001], P[100001];
            int U[100001], V[100001], W[100001];
            int T[100001], X[100001], Y[100001];
            vector<int> join[batch]; stack<int> st;
            bool changed[100001];

            void reset() {
                for(int i = 1; i <= N; i++)
                    P[i] = i, S[i] = 1;
            }

            int findSet(int a) {
                if(P[a] == a) return a;
                return findSet(P[a]);
            }

            void unionSet(int a, int b) {
                a = findSet(a), b = findSet(b);
                if(a == b) return;
                if(S[a] > S[b]) swap(a, b);
                st.push(a); S[b] += S[a];
                P[a] = P[b];
            }

            void restore(int x) {
                while(st.size() > x) {
                    int k = st.top(); st.pop();
                    S[P[k]] -= S[k]; P[k] = k;
                }
            }

            bool compare(int a, int b)  { return Y[a] > Y[b]; }
            bool compare2(int a, int b) { return W[a] > W[b]; }

            int32_t main() {
                ios_base::sync_with_stdio(0);
                cin.tie(0); cout.tie(0);
                cin >> N >> M;
                for(int i = 1; i <= M; i++)
                    cin >> U[i] >> V[i] >> W[i];
                cin >> Q;
                for(int i = 1; i <= Q; i++)
                    cin >> T[i] >> X[i] >> Y[i];

                for(int l = 1; l <= Q; l += batch) {
                    int r = min(Q + 1, l + batch); reset();
                    for(int i = 1; i <= M; i++)
                        changed[i] = false;

                    vector<int> ask, upd, E;
                    for(int i = l; i < r; i++) {
                        if(T[i] == 1) {
                            changed[X[i]] = true;
                            upd.push_back(i);
                        }
                        if(T[i] == 2) ask.push_back(i);
                    }
                    for(int i = 1; i <= M; i++) {
                        if(changed[i]) continue;
                        E.push_back(i);
                    }

                    for(int i = l; i < r; i++) {
                        if(T[i] == 1) W[X[i]] = Y[i];
                        if(T[i] == 2) {
                            join[i - l].clear();
                            for (int j : upd) {
                                if (W[X[j]] >= Y[i])
                                    join[i - l].push_back(X[j]);
                            }
                        }
                    }

                    sort(ask.begin(), ask.end(), compare);
                    sort(E.begin(), E.end(), compare2);

                    int cur = 0;
                    for(int i : ask) {
                        while(cur < E.size() && W[E[cur]] >= Y[i]) {
                            unionSet(U[E[cur]], V[E[cur]]);
                            cur++;
                        }
                        int prev = st.size();
                        for(int j : join[i - l]) unionSet(U[j], V[j]);
                        ans[i] = S[findSet(X[i])];
                        restore(prev);
                    }
                }

                for(int i = 1; i <= Q; i++) {
                    if(T[i] == 1) continue;
                    cout << ans[i] << "\n";
                }
                return 0;
            }

Compilation message (stderr)

bridges.cpp: In function 'void restore(int)':
bridges.cpp:33:33: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |                 while(st.size() > x) {
      |                       ~~~~~~~~~~^~~
bridges.cpp: In function 'int32_t main()':
bridges.cpp:86:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |                         while(cur < E.size() && W[E[cur]] >= Y[i]) {
      |                               ~~~~^~~~~~~~~~

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