oj.uz

Submission #971882

# Submission time Handle Problem Language Result Execution time Memory
971882 2024-04-29T12:43:01 Z ByeWorld Evacuation plan (IZhO18_plan) C++14
41 / 100
 4000 ms 49516 KB 
#include <bits/stdc++.h>
#include <random>
#define ll long long
#define int long long
#define fi first
#define se second
#define pb push_back
#define md ((l+r)>>1)
#define lf (id<<1)
#define rg ((id<<1)|1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
const int MAXN = 2e5+10;
const int MAXA = 1e6+10;
const int INF = 2e9+10;
const int LOG = 30;
const int MOD = 1e9+7;

int n, m, K, Q;
vector <pii> adj[MAXN];
vector <int> vec;
int dis[MAXN], val[MAXN];

priority_queue <pii, vector<pii>, greater<pii>> pq;
void dji(){
	for(int i=1; i<=n; i++) val[i] = INF;
	for(auto in : vec){
		val[in] = 0;
		pq.push({0, in});
	}
	while(!pq.empty()){
		int nw = pq.top().se, dist = pq.top().fi;
		pq.pop();
		// cout << nw << " dist\n";
		if(val[nw] < dist) continue;
		for(auto ed : adj[nw]){
			int nx = ed.fi, wei = ed.se;
			if(val[nx] > val[nw]+wei){
				val[nx] = val[nw]+wei;
				pq.push({val[nx],nx});
			}
		}
	}
}

bool vis[MAXN];
int en, num;
bool cek(int nw){
	if(nw == en) return 1;
	vis[nw] = 1;
	// cout << nw << " nw\n";
	bool can = 0;
	for(auto ed : adj[nw]){
		int nx = ed.fi;
		if(!vis[nx] && val[nx]>=num) can |= cek(nx);
	}
	return can;
}

signed main() {
	// ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(int i=1; i<=m; i++){
		int x, y, w; cin >> x >> y >> w;
		adj[x].pb({y, w}); adj[y].pb({x, w});
	}
	cin >> K;
	for(int i=1; i<=K; i++){
		int p; cin >> p;
		vec.pb(p);
	}
	dji();
	// for(int i=1; i<=n; i++) cout << val[i] << " \n"[i==n];
	cin >> Q;
	while(Q--){
		int x; cin >> x >> en;
		int l=0, r=val[x], mid=0, cnt=-1;
		while(l<=r){
			mid = md; num = mid;
			for(int i=1; i<=n; i++) vis[i] = 0;
			if(cek(x)){
				l = mid+1; cnt = mid;
			} else r = mid-1;
		}
		cout << cnt << '\n';
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8284 KB Output is correct
2 Correct 24 ms 8284 KB Output is correct
3 Correct 16 ms 8392 KB Output is correct
4 Correct 2 ms 8284 KB Output is correct
5 Correct 11 ms 8284 KB Output is correct
6 Correct 7 ms 8396 KB Output is correct
7 Correct 3 ms 8280 KB Output is correct
8 Correct 2 ms 8284 KB Output is correct
9 Correct 7 ms 8284 KB Output is correct
10 Correct 9 ms 8284 KB Output is correct
11 Correct 8 ms 8368 KB Output is correct
12 Correct 19 ms 8280 KB Output is correct
13 Correct 8 ms 8284 KB Output is correct
14 Correct 10 ms 8368 KB Output is correct
15 Correct 9 ms 8280 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8284 KB Output is correct
2 Correct 24 ms 8284 KB Output is correct
3 Correct 16 ms 8392 KB Output is correct
4 Correct 2 ms 8284 KB Output is correct
5 Correct 11 ms 8284 KB Output is correct
6 Correct 7 ms 8396 KB Output is correct
7 Correct 3 ms 8280 KB Output is correct
8 Correct 2 ms 8284 KB Output is correct
9 Correct 7 ms 8284 KB Output is correct
10 Correct 9 ms 8284 KB Output is correct
11 Correct 8 ms 8368 KB Output is correct
12 Correct 19 ms 8280 KB Output is correct
13 Correct 8 ms 8284 KB Output is correct
14 Correct 10 ms 8368 KB Output is correct
15 Correct 9 ms 8280 KB Output is correct
16 Execution timed out 4014 ms 17104 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8284 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 2 ms 8284 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 3 ms 8284 KB Output is correct
6 Correct 3 ms 8460 KB Output is correct
7 Correct 2 ms 8288 KB Output is correct
8 Correct 2 ms 8284 KB Output is correct
9 Correct 2 ms 8284 KB Output is correct
10 Correct 4 ms 8284 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 25952 KB Output is correct
2 Correct 626 ms 48464 KB Output is correct
3 Correct 638 ms 48420 KB Output is correct
4 Correct 95 ms 19276 KB Output is correct
5 Correct 659 ms 48300 KB Output is correct
6 Correct 536 ms 48320 KB Output is correct
7 Correct 577 ms 48408 KB Output is correct
8 Correct 503 ms 48324 KB Output is correct
9 Correct 537 ms 48324 KB Output is correct
10 Correct 597 ms 48356 KB Output is correct
11 Correct 663 ms 48468 KB Output is correct
12 Correct 683 ms 48168 KB Output is correct
13 Correct 606 ms 47824 KB Output is correct
14 Correct 510 ms 47620 KB Output is correct
15 Correct 615 ms 48120 KB Output is correct
16 Correct 642 ms 47864 KB Output is correct
17 Correct 553 ms 48176 KB Output is correct
18 Correct 534 ms 48528 KB Output is correct
19 Correct 70 ms 14928 KB Output is correct
20 Correct 656 ms 48352 KB Output is correct
21 Correct 471 ms 49516 KB Output is correct
22 Correct 85 ms 17684 KB Output is correct
23 Correct 134 ms 15696 KB Output is correct
24 Correct 99 ms 17704 KB Output is correct
25 Correct 83 ms 17588 KB Output is correct
26 Correct 87 ms 16016 KB Output is correct
27 Correct 94 ms 19280 KB Output is correct
28 Correct 99 ms 17600 KB Output is correct
29 Correct 92 ms 19280 KB Output is correct
30 Correct 84 ms 17600 KB Output is correct
31 Correct 101 ms 19148 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8284 KB Output is correct
2 Correct 24 ms 8284 KB Output is correct
3 Correct 16 ms 8392 KB Output is correct
4 Correct 2 ms 8284 KB Output is correct
5 Correct 11 ms 8284 KB Output is correct
6 Correct 7 ms 8396 KB Output is correct
7 Correct 3 ms 8280 KB Output is correct
8 Correct 2 ms 8284 KB Output is correct
9 Correct 7 ms 8284 KB Output is correct
10 Correct 9 ms 8284 KB Output is correct
11 Correct 8 ms 8368 KB Output is correct
12 Correct 19 ms 8280 KB Output is correct
13 Correct 8 ms 8284 KB Output is correct
14 Correct 10 ms 8368 KB Output is correct
15 Correct 9 ms 8280 KB Output is correct
16 Execution timed out 4014 ms 17104 KB Time limit exceeded
17 Halted 0 ms 0 KB -