oj.uz

Submission #940656

# Submission time Handle Problem Language Result Execution time Memory
940656 2024-03-07T12:43:02 Z PenguinsAreCute Cyberland (APIO23_cyberland) C++17
100 / 100
 890 ms 14952 KB 
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define pb emplace_back
#define fi first
#define se second
using di = pair<double,int>;
vector<pair<int,double>> adj[121010];
double dist[121010];
void distra(int N) { // i use jk 4 esc on nvim
	priority_queue<di,vector<di>,greater<di>> pq;
	REP(i,0,N) dist[i]=-1;
	dist[N]=0;
	pq.push(di(0,N));
	while(pq.size()) {
		di x = pq.top(); pq.pop();
		if(abs(x.fi-dist[x.se]) > 1e-5) continue;
		for(auto i: adj[x.se]) if(dist[i.fi]<-0.5||dist[i.fi]>x.fi+i.se) {
			dist[i.fi]=x.fi+i.se;
			pq.push(di(dist[i.fi],i.fi));
		}
	}
}
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
	K=min(K,70);
	double ans = 1e15;
	REP(i,0,N+1) adj[i].clear();
	REP(i,0,M) {
		if(x[i]!=H) adj[x[i]].pb(y[i],c[i]);
		if(y[i]!=H) adj[y[i]].pb(x[i],c[i]);
	}
	adj[N].pb(0,0);
	distra(N);
	REP(i,0,N) if(!arr[i] && dist[i]>-0.5) adj[N].pb(i,0);
	REP(i,0,K+1) {
		distra(N);
		if(dist[H]>-0.5) ans=min(ans,dist[H]);
		adj[N].clear();
		REP(i,0,N) if(arr[i]==2) {
			double nxtDist = 1e15;
			for(auto j: adj[i]) if(j.fi!=H&&dist[j.fi]>-0.5) nxtDist=min(nxtDist,dist[j.fi]+j.se);
			if(nxtDist<9e14) adj[N].pb(i,nxtDist/2.0);
		}
	}
    return (ans>=9e14?-1:ans);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 4444 KB Correct.
2 Correct 29 ms 4444 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4952 KB Correct.
2 Correct 28 ms 5268 KB Correct.
3 Correct 24 ms 5112 KB Correct.
4 Correct 25 ms 5212 KB Correct.
5 Correct 24 ms 5208 KB Correct.
6 Correct 26 ms 5920 KB Correct.
7 Correct 32 ms 5976 KB Correct.
8 Correct 15 ms 6236 KB Correct.
9 Correct 23 ms 4956 KB Correct.
10 Correct 23 ms 4876 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 5660 KB Correct.
2 Correct 26 ms 5724 KB Correct.
3 Correct 26 ms 5744 KB Correct.
4 Correct 25 ms 4952 KB Correct.
5 Correct 25 ms 4952 KB Correct.
6 Correct 6 ms 5212 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 10472 KB Correct.
2 Correct 85 ms 5420 KB Correct.
3 Correct 77 ms 5252 KB Correct.
4 Correct 79 ms 5340 KB Correct.
5 Correct 47 ms 4956 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 5220 KB Correct.
2 Correct 22 ms 5188 KB Correct.
3 Correct 22 ms 5168 KB Correct.
4 Correct 23 ms 6304 KB Correct.
5 Correct 20 ms 4720 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 5456 KB Correct.
2 Correct 20 ms 5208 KB Correct.
3 Correct 40 ms 12368 KB Correct.
4 Correct 17 ms 5720 KB Correct.
5 Correct 23 ms 4952 KB Correct.
6 Correct 22 ms 5404 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 5484 KB Correct.
2 Correct 15 ms 4444 KB Correct.
3 Correct 305 ms 14952 KB Correct.
4 Correct 215 ms 8640 KB Correct.
5 Correct 311 ms 13356 KB Correct.
6 Correct 139 ms 11912 KB Correct.
7 Correct 218 ms 8340 KB Correct.
8 Correct 167 ms 6612 KB Correct.
9 Correct 86 ms 5344 KB Correct.
10 Correct 76 ms 5212 KB Correct.
11 Correct 143 ms 6300 KB Correct.
12 Correct 87 ms 5456 KB Correct.
13 Correct 86 ms 5444 KB Correct.
14 Correct 225 ms 10160 KB Correct.
15 Correct 193 ms 7468 KB Correct.
16 Correct 86 ms 5792 KB Correct.
17 Correct 97 ms 5344 KB Correct.
18 Correct 92 ms 5324 KB Correct.
19 Correct 269 ms 6232 KB Correct.
20 Correct 8 ms 4196 KB Correct.
21 Correct 7 ms 4188 KB Correct.
22 Correct 12 ms 4848 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 5476 KB Correct.
2 Correct 30 ms 4440 KB Correct.
3 Correct 186 ms 14420 KB Correct.
4 Correct 237 ms 7120 KB Correct.
5 Correct 658 ms 13428 KB Correct.
6 Correct 302 ms 11932 KB Correct.
7 Correct 402 ms 10380 KB Correct.
8 Correct 186 ms 6320 KB Correct.
9 Correct 135 ms 5260 KB Correct.
10 Correct 131 ms 5204 KB Correct.
11 Correct 141 ms 5468 KB Correct.
12 Correct 166 ms 5400 KB Correct.
13 Correct 155 ms 5488 KB Correct.
14 Correct 890 ms 12332 KB Correct.
15 Correct 685 ms 10744 KB Correct.
16 Correct 351 ms 8232 KB Correct.
17 Correct 219 ms 6412 KB Correct.
18 Correct 143 ms 5456 KB Correct.
19 Correct 173 ms 5448 KB Correct.
20 Correct 164 ms 5584 KB Correct.
21 Correct 530 ms 6032 KB Correct.
22 Correct 9 ms 4196 KB Correct.
23 Correct 11 ms 4228 KB Correct.
24 Correct 22 ms 4952 KB Correct.