Submission #636583

#	Time	Username	Problem	Language	Result	Execution time	Memory
636583		MohamedFaresNebili	Bridges (APIO19_bridges)	C++14	14 / 100	1614 ms	29116 KiB

bridges

#include <bits/stdc++.h>

            using namespace std;

            const int INF = INT32_MAX;
            const int batch = 1001;

            int N, M, Q, P[100001], S[100001];
            int U[100001], V[100001], D[100001];
            int T[100001], R[100001], W[100001];
            int ans[100001]; stack<int> St;

            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 A, int B)  { return W[A] > W[B]; }
            bool compare2(int A, int B) { return D[A] > D[B]; }

            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] >> D[l];
                cin >> Q;
                for(int l = 1; l <= Q; l++)
                    cin >> T[l] >> R[l] >> W[l];

                for(int l = 1; l <= Q; l += batch) {
                    reset(); int r = min(Q, l + batch - 1);
                    vector<bool> unchanged(M + 1, false);
                    vector<int> upd, ask;
                    for(int i = l; i <= r; i++) {
                        if(T[i] == 1) {
                            unchanged[R[i]] = true;
                            upd.push_back(i);
                        }
                        if(T[i] == 2) ask.push_back(i);
                    }
                    vector<int> G, B[batch + 2];
                    for(int i = 1; i <= M; i++)  {
                        if(!unchanged[i]) G.push_back(i);
                    }
                    for(int i = l; i <= r; i++) {
                        if(T[i] == 1) D[R[i]] = W[i];
                        if(T[i] == 2) {
                            for(auto u : upd) {
                                if(D[R[u]] >= W[i])
                                    B[i - l].push_back(R[u]);
                            }
                        }
                    }

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

                    int cur = 0;
                    for(auto u : ask) {
                        while(cur < G.size() && D[G[cur]] >= W[u]) {
                            unionSet(U[G[cur]], V[G[cur]]); ++cur;
                        }
                        int prev = St.size();
                        for(auto v : B[u - l]) unionSet(U[v], V[v]);
                        ans[u] = S[findSet(R[u])];
                        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(int)':
bridges.cpp:28:33: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |                 while(St.size() > v) {
      |                       ~~~~~~~~~~^~~
bridges.cpp: In function 'int32_t main()':
bridges.cpp:76:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |                         while(cur < G.size() && D[G[cur]] >= W[u]) {
      |                               ~~~~^~~~~~~~~~

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