Submission #1187163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187163		inesfi	Bridges (APIO19_bridges)	C++20	13 / 100	72 ms	580 KiB

bridges

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

#define endl "\n"
#define int long long

const int TAILLEMAXI=1002;
vector<int> adja[TAILLEMAXI];
vector<tuple<int,int,int>> aretes;
int dejavu[TAILLEMAXI];

int dfs(int a,int p){
    if (dejavu[a]==1){
        return 0;
    }
    dejavu[a]=1;
    int r=1;
    for (auto i:adja[a]){
        if (get<2>(aretes[i])>=p){
            if (get<0>(aretes[i])==a){
                r+=dfs(get<1>(aretes[i]),p);
            }
            else {
                r+=dfs(get<0>(aretes[i]),p);
            }
        }
    }
    return r;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int nbnoeuds,nbaretes;
    cin>>nbnoeuds>>nbaretes;
    for (int i=0;i<nbaretes;i++){
        int a,b,p;
        cin>>a>>b>>p;
        a--;
        b--;
        adja[a].push_back(i);
        adja[b].push_back(i);
        aretes.push_back({a,b,p});
    }
    int nbquest;
    cin>>nbquest;
    for (int i=0;i<nbquest;i++){
        int type;
        cin>>type;
        if (type==1){
            int a,p;
            cin>>a>>p;
            a--;
            get<2>(aretes[a])=p;
        }
        else {
            int a,p;
            cin>>a>>p;
            for (int i=0;i<nbnoeuds;i++){
                dejavu[i]=0;
            }
            cout<<dfs(a-1,p)<<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