oj.uz

답안 #1067490

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1067490 2024-08-20T18:01:32 Z lovrot 사이버랜드 (APIO23_cyberland) C++17
8 / 100
 371 ms 40784 KB 
#include "cyberland.h"
#include <vector>
#include <algorithm>
#include <set>
#include <cstring>

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define X first
#define Y second
#define PB push_back

using namespace std; 

typedef long long ll;
typedef pair<int, int> pii;

const int P = 60;
const int N = 1e5 + 10;
const double OO = 1e18;
const double TSH = 1e-9;

int k, n, h;
vector<pii> g[N];

char con[N], bio[N][P], type[N];
double dp[N][P], ans;
set<pair<double, pii>> s;

void check(int u) { 
	if(con[u]) { 
		return;
	}
	con[u] = 1;
	if(u == h) {
		return; 
	}
	for(pii e : g[u]) { 
		check(e.X);
	}
}

void dijkstra() {
	for(int i = 0; i < n; ++i) { 
		for(int j = 0; j < P; ++j) { 
			dp[i][j] = OO;
			bio[i][j] = 0;
		}
	}

	dp[h][0] = 0;
	s.insert({dp[h][0], {h, 0}});

	for(; !s.empty(); ) { 
		int u = s.begin()->Y.X;
		int p = s.begin()->Y.Y;
		s.erase(s.begin());
		if(bio[u][p] || type[u] == 0) { 
			ans = min(ans, dp[u][p]);
		}
		bio[u][p] = 1;
		for(pii e : g[u]) { 
			int v = e.X, w = e.Y, pp = type[v] == 2 ? min(p + 1, k) : p;
			if(!bio[v][pp] && abs(dp[v][pp] - dp[u][p] - (double) w / (1LL << p)) > TSH) { 
				dp[v][pp] = dp[u][p] + (double) w / (1LL << p);
				s.insert({dp[v][pp], {v, pp}});
			}
		}
	}
}

double solve(int nn, int m, int kk, int hh, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
	n = nn;
	k = min(kk, P - 1);
	h = hh;

	for(int i = 0; i < n; ++i) { 
		con[i] = 0;
		g[i].clear();
	}

	for(int i = 0; i < m; ++i) {
		g[x[i]].PB({y[i], c[i]});
		g[y[i]].PB({x[i], c[i]});
	}
	for(int i = 0; i < n; ++i) { 
		type[i] = arr[i];
	}
	type[0] = 0;

	check(0);
	
	if(!con[h]) { 
		return -1;
	}
	
	ans = OO;
	dijkstra();
    return ans;
}

Subtask #1
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 6492 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 8792 KB Correct.
2 Correct 21 ms 8756 KB Correct.
3 Correct 20 ms 8536 KB Correct.
4 Correct 21 ms 8536 KB Correct.
5 Correct 21 ms 8796 KB Correct.
6 Correct 19 ms 15560 KB Correct.
7 Correct 26 ms 15452 KB Correct.
8 Correct 12 ms 20280 KB Correct.
9 Correct 18 ms 6492 KB Correct.
10 Correct 18 ms 6528 KB Correct.

Subtask #3
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 24 ms 8540 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 29 ms 40784 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 18 ms 8792 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 20 ms 8796 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 188 ms 8796 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 371 ms 9292 KB Wrong Answer.
2 Halted 0 ms 0 KB -