Submission #934043

#	Time	Username	Problem	Language	Result	Execution time	Memory
934043		vjudge1	Bridges (APIO19_bridges)	C++14	13 / 100	3086 ms	10080 KiB

bridges

#include <bits/stdc++.h>
#define TAM 50002
#define noA first
#define noB second
using namespace std;
typedef long long ll;

struct node{
    vector<pair<ll, ll>> conex;
};

ll n, m, q, a, b, c, test;
node tree[TAM];
vector <ll> brig;
ll visited[TAM];

ll dp(ll index, ll car){

    ll co = 0;
    visited[index] = test;
    for (pair <ll, ll> i : tree[index].conex) {
        if(visited[i.noA] != test && brig[i.noB] >= car)
            co += dp(i.noA, car);
    }
    return co + 1;
}

int main(){
    cout.tie(0); cin.tie(0);
    ios::sync_with_stdio(0);

    cin >> n >> m;
    for(ll i = 0; i < m; i++){
        cin >> a >> b >> c;
        tree[a].conex.push_back({b, i});
        tree[b].conex.push_back({a, i});
        brig.push_back(c);
    }

    cin >> q;
    for(ll i = 0; i < q; i++){
        cin >> a >> b >> c;
        if(a == 1){
            b--;
            brig[b] = c;
        }else{
            test++;
            cout << dp(b, c) << endl;
        }
    }
    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