oj.uz

Submission #406729

# Submission time Handle Problem Language Result Execution time Memory
406729 2021-05-18T03:52:42 Z amunduzbaev Bridges (APIO19_bridges) C++14
0 / 100
 65 ms 20600 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Runtime error 5 ms 5452 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 12380 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 10360 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 65 ms 20600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 12380 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Runtime error 5 ms 5452 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -