Submission #211394

#	Time	Username	Problem	Language	Result	Execution time	Memory
211394		VEGAnn	Bridges (APIO19_bridges)	C++14	13 / 100	3088 ms	7544 KiB

bridges

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define pll pair<ll, ll>
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long ll;
const int N = 50100;
const int M = 100100;
const int oo = 2e9;
queue<int> q;
vector<int> g[N];
int n, m, U[M], V[M], D[M], dst[N];

int main(){

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#else
    ios_base::sync_with_stdio(0); cin.tie(0);
#endif // _LOCAL

    cin >> n >> m;

    for (int i = 0; i < m; i++){
        cin >> U[i] >> V[i] >> D[i];
        U[i]--; V[i]--;

        g[U[i]].PB(i);
        g[V[i]].PB(i);
    }

    int qq; cin >> qq;

    for (; qq; qq--){
        int tp, l, r; cin >> tp >> l >> r;

        if (tp == 1){
            D[l - 1] = r;
        } else {
            l--;
            while (sz(q)) q.pop();

            fill(dst, dst + n, oo);
            q.push(l);
            dst[l] = 0;

            int ans = 0;

            while (sz(q)){
                int v = q.front(); q.pop();
                ans++;

                for (int nm : g[v]){
                    int u = (U[nm] == v ? V[nm] : U[nm]);

                    if (dst[u] == oo && D[nm] >= r){
                        dst[u] = dst[v] + 1;
                        q.push(u);
                    }
                }
            }

            cout << ans << '\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