Submission #406729

#	Time	Username	Problem	Language	Result	Execution time	Memory
406729		amunduzbaev	Bridges (APIO19_bridges)	C++14	0 / 100	65 ms	20600 KiB

bridges

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

#define pb push_back
#define int long long
#define ff first
#define ss second

template<class T> bool umin(T& a, const T b) { if(a > b) { a = b; return 1; } return 0; }
template<class T> bool umax(T& a, const T b) { if(a < b) { a = b; return 1; } return 0; }

const int mod = 1e9+7;
const int N = 1e5+5;

int n, m, q, mn[N];
vector<pair<int, int>> edges[N];
array<int, 3> tt[N];

int dis[N];

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int a, b, c; cin>>a>>b>>c;
		edges[a].pb({b, c}), edges[b].pb({a, c});
		tt[i] = {a, b, c};
	} cin>>q;
	if(n <= 1000 && m <= 1000 && q <= 1000){
		while(q--){
			int t; cin>>t;
			if(t == 1){
				int br, w; cin>>br>>w, br--;
				int a = tt[br][0], b = tt[br][1], c = tt[br][2]; tt[br][2] = w;
				for(auto& x : edges[a]) if(x.ff == b && x.ss == c) { x.ss = w; break; }
				for(auto& x : edges[b]) if(x.ff == a && x.ss == c) { x.ss = w; break; }
			} else {
				int u, w; cin>>u>>w;
				for(int i=1;i<=n;i++) mn[i] = -mod;
				priority_queue<pair<int, int>> qq;
				mn[u] = mod; qq.push({mod, u});
				while(!qq.empty()){
					auto u = qq.top(); qq.pop();
					if(mn[u.ss] > u.ff) continue;
					for(auto x : edges[u.ss])
						if(umax(mn[x.ff], min(mn[u.ss], x.ss))) qq.push({mn[x.ff], x.ff});
				} int rr = 0;
				for(int i=1;i<=n;i++) if(mn[i] >= w) rr++;
				cout<<rr<<"\n";
			}
		}
	} else assert(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