Submission #716737

#	Time	Username	Problem	Language	Result	Execution time	Memory
716737		Seb	Bridges (APIO19_bridges)	C++17	0 / 100	3073 ms	10512 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define f first
#define s second

vector <pair<ll,ll>> g[50005];
bool vis[50005];
ll ans;

void dfs(ll nodo, ll peso) {
    vis[nodo] = true;
    ans++;
    for (auto it=g[nodo].begin();it!=g[nodo].end();it++) {
        if (vis[it->f]==false && it->s >= peso) {
            dfs(it->f,peso);
        }
    }
    return;
}

ll bin(ll in, ll ini, ll fin, ll tar) {
    ll mid = (ini+fin)/2;
    if (ini==fin) return ini-1;
    if (g[in][mid].f>tar) return bin(in,ini,mid,tar);
    else return bin(in,mid+1,fin,tar);
}

int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
ll n,m,i,t,b,r,s,w,q,aux;
cin>>n>>m;
ll u[m],v[m],d[m];
for (i=0;i<m;i++) {
    cin>>u[i]>>v[i]>>d[i];
    g[u[i]].push_back({v[i],d[i]});
    g[v[i]].push_back({u[i],d[i]});
}
for (i=1;i<=n;i++) sort(g[i].begin(),g[i].end());
cin>>q;
while (q--) {
    cin>>t;
    if (t==1) {
        cin>>b>>r;
        aux = bin(v[b-1],0,g[v[b-1]].size(),u[b-1]);
        if (aux!=-1) g[v[b-1]][aux].s = r;
        aux = bin(u[b-1],0,g[u[b-1]].size(),v[b-1]);
        if (aux!=-1) g[u[b-1]][aux].s = r;
    }
    else {
        cin>>s>>w;
        for (i=0;i<=n;i++) vis[i] = false;
        ans = 0;
        dfs(s,w);
        cout<<ans<<"\n";
    }
}
return 0;
}

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