Submission #983117

#	Time	Username	Problem	Language	Result	Execution time	Memory
983117		vjudge1	Bridges (APIO19_bridges)	C++17	13 / 100	3053 ms	9748 KiB

bridges

#include<bits/stdc++.h>
#define sz size()
#define ll long long
using namespace std;

void solve()
{
    ll n, m, Q, i, j, k;
    cin >> n >> m;

    vector<pair<ll, ll>> v[n + 1];
    ll x[m + 1], y[m + 1], z[m + 1];
    for(i = 1; i <= m; ++i)
    {
        ll a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
        x[i] = a, y[i] = b, z[i] = c;
    }

    cin >> Q;
    while(Q--)
    {
        ll t, u, k;
        cin >> t >> u >> k;
        if(t == 1)
        {
            for(auto &i : v[x[u]])
                if(i.first == y[u] && i.second == z[u]){
                    i.second = k;
                    break;
                }
            for(auto &i : v[y[u]])
                if(i.first == x[u] && i.second == z[u]){
                    i.second = k;
                    break;
                }
            z[u] = k;
            continue;
        }
        ll us[n + 1] = {};
        queue<ll> q;
        q.push(u);
        us[u] = 1;
        ll ans = 1;
        while(q.sz)
        {
            ll s = q.front();
            q.pop();
            for(auto [t, c] : v[s])
            {
                if(us[t] || c < k) continue;
                q.push(t);
                us[t] = 1;
                ++ans;
            }
        }
        cout << ans << '\n';
    }

}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    solve();
}

Compilation message (stderr)

bridges.cpp: In function 'void solve()':
bridges.cpp:8:20: warning: unused variable 'j' [-Wunused-variable]
    8 |     ll n, m, Q, i, j, k;
      |                    ^
bridges.cpp:8:23: warning: unused variable 'k' [-Wunused-variable]
    8 |     ll n, m, Q, i, j, k;
      |                       ^

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