Submission #636534

#	Time	Username	Problem	Language	Result	Execution time	Memory
636534		MohamedFaresNebili	Bridges (APIO19_bridges)	C++14	13 / 100	3067 ms	10244 KiB

bridges

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")

            using namespace std;

            using ll = long long;

            #define int ll

            const int INF = LLONG_MAX;

            int N, M, Q;
            vector<array<int, 4>> E;
            vector<pair<int, int>> adj[50005];

            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].size(), adj[V].size()});
                    adj[U].push_back({V, D}); adj[V].push_back({U, D});
                }
                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];
                        int i = E[B][2], j = E[B][3];
                        adj[U][i].second = R, adj[V][j].second = R;
                    }
                    if(t == 2) {
                        int S, W; cin >> S >> W;
                        vector<bool> vis(N + 1, 0);
                        queue<int> q; q.push(S); int res = 0;
                        while(!q.empty()) {
                            int A = q.front(); q.pop();
                            if(vis[A]) continue;
                            vis[A] = 1; ++res;
                            for(auto u : adj[A]) {
                                if(vis[u.first] || u.second < W) continue;
                                q.push(u.first);
                            }
                        }
                        cout << res << "\n";
                    }
                }
                return 0;
            }

Compilation message (stderr)

bridges.cpp: In function 'int32_t main()':
bridges.cpp:23:51: warning: narrowing conversion of 'adj[U].std::vector<std::pair<long long int, long long int> >::size()' from 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
   23 |                     E.push_back({U, V, adj[U].size(), adj[V].size()});
      |                                        ~~~~~~~~~~~^~
bridges.cpp:23:66: warning: narrowing conversion of 'adj[V].std::vector<std::pair<long long int, long long int> >::size()' from 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
   23 |                     E.push_back({U, V, adj[U].size(), adj[V].size()});
      |                                                       ~~~~~~~~~~~^~

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