Submission #252146

#	Time	Username	Problem	Language	Result	Execution time	Memory
252146		Erkhemkhuu	Bridges (APIO19_bridges)	C++17	13 / 100	101 ms	48768 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
const ll N = 1005;
bool vis[N];
tuple <ll, ll, ll> brid[N];
vector <vector <ll> > adj(N);
vector <ll> wp[N][N];
ll dfs(ll v, ll w) {
    ll ans = 1;
    vis[v] = true;
    for(auto &u: adj[v])
        for(auto &x: wp[v][u])
            if(!vis[u] && w <= x) ans += dfs(u, w);
    return ans;
}
int main() {
    ll n, m, i, v, u, w, q, t, l, r;
    cin >> n >> m;
    for(i = 0; i < m; i++) {
        cin >> v >> u >> w;
        v--; u--;
        adj[v].pb(u);
        adj[u].pb(v);
        wp[v][u].pb(w);
        wp[u][v].pb(w);
        brid[i] = {v, u, wp[v][u].size() - 1};
    }
    cin >> q;
    while(q--) {
        cin >> t >> l >> r;
        l--;
        if(t == 1) {
            auto temp = brid[l];
            ll x = get <0> (temp);
            ll y = get <1> (temp);
            ll z = get <2> (temp);
            wp[x][y][z] = wp[y][x][z] = r;
        }
        else {
            memset(vis, false, sizeof(vis));
            cout << dfs(l, r) << "\n";
        }
    }
    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