Submission #725044

#	Time	Username	Problem	Language	Result	Execution time	Memory
725044		inventiontime	Bridges (APIO19_bridges)	C++17	13 / 100	3057 ms	21020 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

#define int ll
#define endl '\n' //comment for interactive
#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

#define pb push_back
#define re resize
#define ff first
#define ss second

#define all(x) (x).begin(), (x).end()
#define all1(x) (x).begin()+1, (x).end()
#define loop(i, n) for(int i = 0; i < n; i++)
#define loop1(i, n) for(int i = 1; i <= n; i++)

#define print(x) cout << #x << ": " << x << endl << flush

typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
typedef array<int, 3> ti;
typedef vector<ii> vii;
typedef vector<ti> vti;
typedef vector<vi> vvi;
typedef priority_queue<int> pq;

template<class T> bool ckmin(T&a, T b) { bool B = a > b; a = min(a, b); return B; }
template<class T> bool ckmax(T&a, T b) { bool B = a < b; a = max(a, b); return B; }

const int inf = 1e17;

void solve() {

    int n, m;
    cin >> n >> m;

    vti edge(m+1);
    loop1(i, m) {
        int u, v, d;
        cin >> u >> v >> d;
        edge[i] = {d, u, v};
    }

    vector<multiset<ii>> adj(n+1);
    loop1(i, m) {
        auto [d, u, v] = edge[i];
        adj[u].insert({d, v});
        adj[v].insert({d, u});
    }

    int q; cin >> q;
    loop1(qi, q) {
        int t; cin >> t;
        if(t == 1) {
            int b, r; cin >> b >> r;
            auto [d, u, v] = edge[b];
            adj[u].erase(adj[u].find({d, v}));
            adj[v].erase(adj[v].find({d, u}));
            adj[u].insert({r, v});
            adj[v].insert({r, u});
            edge[b] = {r, u, v};
        } else if(t == 2) {
            int s, w; cin >> s >> w;
            vector<bool> vis(n+1);
            auto dfs = [&] (int u, auto dfs) -> void {
                for(auto [d, v] : adj[u]) if(!vis[v] and d >= w) {
                    vis[v] = true;
                    dfs(v, dfs);
                }
            };
            vis[s] = true;
            dfs(s, dfs);
            cout << accumulate(all(vis), 0) << endl;
        }
    }


}

signed main() {

    fast_io;

    int t = 1; //cin >> t;
    while(t--)
        solve();

    return 0;

}

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