Submission #636593

#	Time	Username	Problem	Language	Result	Execution time	Memory
636593		MohamedFaresNebili	Bridges (APIO19_bridges)	C++14	14 / 100	1774 ms	51508 KiB

bridges

#include <bits/stdc++.h>

            using namespace std;
            using ll = long long;

            const int batch = 1001;

            #define int ll

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


            void reset() {
                for(int l = 1; l <= N; l++)
                    P[l] = l, S[l] = 1;
            }
            int findSet(int v) {
                if(P[v] == v) return v;
                return P[v] = findSet(P[v]);
            }
            void unionSet(int u, int v) {
                u = findSet(u), v = findSet(v);
                if(u == v) return;
                if(S[u] > S[v]) swap(u, v);
                st.push(u); S[v] += S[u];
                P[u] = v;
            }
            void restore(int v) {
                while(st.size() > v) {
                    int K = st.top(); st.pop();
                    S[P[K]] -= S[K]; P[K] = K;
                }
            }
            bool compare(int u, int v) {
                return Y[u] > Y[v];
            }
            bool compare2(int u, int v) {
                return W[u] > W[v];
            }

            int32_t main() {
                ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                cin >> N >> M;
                for(int l = 1; l <= M; l++)
                    cin >> U[l] >> V[l] >> W[l];
                cin >> Q;
                for(int l = 1; l <= Q; l++)
                    cin >> T[l] >> X[l] >> Y[l];
                for(int l = 1; l <= Q; l += batch) {
                    int r = min(Q, l + batch - 1); reset();
                    for(int i = 1; i <= M; i++) changed[i] = 0;
                    vector<int> ask, upd, E;
                    for(int i = l; i <= r; i++) {
                        if(T[i] == 1) {
                            changed[X[i]] = 1;
                            upd.push_back(i);
                        }
                        if(T[i] == 2) ask.push_back(i);
                    }
                    for(int i = 1; i <= M; i++)
                        if(!changed[i]) E.push_back(i);
                    for(int i = l; i <= r; i++) {
                        if(T[i] == 1) W[X[i]] = Y[i];
                        else {
                            join[i - l].clear();
                            for(auto 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(auto i : ask) {
                        while(cur < E.size() && W[E[cur]] >= Y[i]) {
                            unionSet(U[E[cur]], V[E[cur]]); cur++;
                        }
                        int prev = st.size();
                        for(auto j : join[i - l]) unionSet(U[j], V[j]);
                        ans[i] = S[findSet(X[i])];
                        restore(prev);
                    }
                }
                for(int l = 1; l <= Q; l++) {
                    if(T[l] == 1) continue;
                    cout << ans[l] << "\n";
                }
                return 0;
            }

Compilation message (stderr)

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

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