oj.uz

Submission #1009298

# Submission time Handle Problem Language Result Execution time Memory
1009298 2024-06-27T11:01:39 Z pcc Cyberland (APIO23_cyberland) C++17
100 / 100
 1976 ms 11652 KB 
#include "cyberland.h"

#include <vector>
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")
using namespace std;
#define ld double
#define pii pair<int,int>
#define fs first
#define sc second
#define mt make_tuple

const ld inf = 1e15;
const int mxn  = 2e5+10;
const int lim = 70;
ld dist[mxn];
int head[mxn*2],nid[mxn*2],to[mxn*2],wei[mxn*2];
int ptr = 0;
bitset<mxn> able;
int N,M;

void add_edge(int a,int b,int c){
	ptr++;
	nid[ptr] = head[a];
	head[a] = ptr;
	to[ptr] = b;
	wei[ptr] = c;
	return;
}

namespace DIJKSTRA{
	bitset<mxn> done;
	priority_queue<pair<ld,int>,vector<pair<ld,int>>,greater<pair<ld,int>>> pq;
	void GO(int ban){
		for(int i = 0;i<N;i++){
			dist[i+N] = inf;
			done[i] = done[i+N] = false;
			if(ban != i&&able[i]){
				pq.push(make_pair(dist[i],i));
			}
		}
		while(!pq.empty()){
			auto now = pq.top().sc;
			pq.pop();
			if(done[now])continue;
			done[now] = true;
			int pid = (now<N?now:now-N);
			for(int eid = head[pid];eid;eid = nid[eid]){
				int w = wei[eid],nxt = to[eid];
				if(!able[nxt]||done[nxt+N])continue;
				if(dist[nxt+N] > dist[now]+w){
					dist[nxt+N] = dist[now]+w;
					if(nxt != ban)pq.push(make_pair(dist[nxt+N],nxt+N));
				}
			}
		}
		return;
	}
}

void init(){
	fill(head,head+N,0);
	ptr = 0;
}

double solve(int NN, int MM, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> z, std::vector<int> arr) {
	init();
	N = NN,M = MM;
	for(int i = 0;i<M;i++){
		int a = x[i],b = y[i],c = z[i];
		add_edge(a,b,c);
		add_edge(b,a,c);
	}
	for(int i = 0;i<N*2;i++)able[i] = true;
	for(int i = 0;i<N;i++)dist[i] = inf;
	dist[0] = 0;
	DIJKSTRA::GO(H);
	for(int i = 0;i<N;i++){
		able[i] = able[i+N] = (min(dist[i],dist[i+N])+1<inf);
	}
	for(int i = 0;i<N;i++){
		if(able[i]&&arr[i] == 0)dist[i] = 0;
		else dist[i] = inf;
	}
	if(!able[H])return -1;
	dist[0] = 0;
	ld ans = inf;
	for(int i = 0;i<=min(K,lim);i++){
		DIJKSTRA::GO(H);
		ans = min({ans,dist[H],dist[H+N]});
		if(i+1<=min(K,lim)&&arr[H] == 2)ans = min({ans,dist[H+N]/2});
		for(int j = 0;j<N;j++){
			dist[j] = min(dist[j],dist[j+N]);
			if(able[j]&&arr[j] == 2)dist[j] = min(dist[j],dist[j+N]/2);
		}
		dist[H] = inf;
	}
	return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 4700 KB Correct.
2 Correct 21 ms 4700 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 4656 KB Correct.
2 Correct 258 ms 4704 KB Correct.
3 Correct 215 ms 4676 KB Correct.
4 Correct 231 ms 4440 KB Correct.
5 Correct 224 ms 4688 KB Correct.
6 Correct 382 ms 5456 KB Correct.
7 Correct 468 ms 5456 KB Correct.
8 Correct 203 ms 6104 KB Correct.
9 Correct 112 ms 4612 KB Correct.
10 Correct 108 ms 4444 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 4656 KB Correct.
2 Correct 245 ms 4444 KB Correct.
3 Correct 221 ms 4652 KB Correct.
4 Correct 131 ms 4604 KB Correct.
5 Correct 132 ms 4440 KB Correct.
6 Correct 84 ms 5340 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 8656 KB Correct.
2 Correct 173 ms 4688 KB Correct.
3 Correct 151 ms 4680 KB Correct.
4 Correct 163 ms 4688 KB Correct.
5 Correct 78 ms 4440 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 4688 KB Correct.
2 Correct 88 ms 4444 KB Correct.
3 Correct 97 ms 4640 KB Correct.
4 Correct 216 ms 5364 KB Correct.
5 Correct 57 ms 4444 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 4672 KB Correct.
2 Correct 83 ms 4680 KB Correct.
3 Correct 30 ms 10700 KB Correct.
4 Correct 138 ms 5248 KB Correct.
5 Correct 69 ms 4444 KB Correct.
6 Correct 128 ms 4692 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 4640 KB Correct.
2 Correct 33 ms 4700 KB Correct.
3 Correct 737 ms 11652 KB Correct.
4 Correct 600 ms 6244 KB Correct.
5 Correct 679 ms 8656 KB Correct.
6 Correct 348 ms 7384 KB Correct.
7 Correct 575 ms 6348 KB Correct.
8 Correct 441 ms 4944 KB Correct.
9 Correct 130 ms 4688 KB Correct.
10 Correct 115 ms 4656 KB Correct.
11 Correct 355 ms 4688 KB Correct.
12 Correct 156 ms 4644 KB Correct.
13 Correct 150 ms 4692 KB Correct.
14 Correct 457 ms 8140 KB Correct.
15 Correct 486 ms 5444 KB Correct.
16 Correct 134 ms 4688 KB Correct.
17 Correct 176 ms 4644 KB Correct.
18 Correct 146 ms 4688 KB Correct.
19 Correct 493 ms 4440 KB Correct.
20 Correct 7 ms 4440 KB Correct.
21 Correct 10 ms 4640 KB Correct.
22 Correct 23 ms 4956 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 4444 KB Correct.
2 Correct 59 ms 4700 KB Correct.
3 Correct 1559 ms 11608 KB Correct.
4 Correct 626 ms 7088 KB Correct.
5 Correct 1580 ms 10452 KB Correct.
6 Correct 773 ms 7892 KB Correct.
7 Correct 890 ms 9856 KB Correct.
8 Correct 521 ms 6784 KB Correct.
9 Correct 253 ms 5460 KB Correct.
10 Correct 206 ms 5456 KB Correct.
11 Correct 178 ms 5716 KB Correct.
12 Correct 283 ms 5500 KB Correct.
13 Correct 277 ms 5648 KB Correct.
14 Correct 1937 ms 9616 KB Correct.
15 Correct 1976 ms 10256 KB Correct.
16 Correct 870 ms 7796 KB Correct.
17 Correct 610 ms 6740 KB Correct.
18 Correct 244 ms 5716 KB Correct.
19 Correct 346 ms 5640 KB Correct.
20 Correct 248 ms 5656 KB Correct.
21 Correct 893 ms 6584 KB Correct.
22 Correct 12 ms 4440 KB Correct.
23 Correct 17 ms 4700 KB Correct.
24 Correct 48 ms 4956 KB Correct.