oj.uz

답안 #758686

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
758686 2023-06-15T06:14:28 Z OrazB 사이버랜드 (APIO23_cyberland) C++17
44 / 100
 860 ms 2097152 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
//set.find_by_order(x) x-position value
//set.order_of_key(x) number of strictly less elements don't need *set.??
#define N 100005
#define wr cout << "Continue debugging\n";
#define all(x) (x).begin(), (x).end()
#define ll long long int
#define pii pair <int, int>
#define pb push_back
#define ff first
#define ss second

vector<pii> E[N];

void dfs(int nd, int h, vector<int> arr, priority_queue<pii> &q, vector<double> &dis, vector<bool> &vis){
	if (!arr[nd]){
		q.push({0, nd});
		dis[nd] = 0;
	} 
	vis[nd] = 1;
	for (auto i : E[nd]){
		if (vis[i.ff] or i.ff == h) continue;
		dfs(i.ff, h, arr, q, dis, vis);	
	}
}

double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){
	for (int i = 0; i < n; i++) E[i].clear();
	for (int i = 0; i < m; i++){
		E[x[i]].pb({y[i], c[i]});
		E[y[i]].pb({x[i], c[i]});	
	}
	vector<bool> vis(n, 0);
	vector<double> dis(n, 1e18);
	vector<int> cur(n, 0);
	priority_queue<pii> q;
	q.push({0, 0});
	dis[0] = 0;
	dfs(0, h, arr, q, dis, vis);
	while(!q.empty()){
		int x = q.top().ss;
		q.pop();
		for (auto i : E[x]){
			double res = dis[x]+i.ss, t = 0;
			if (arr[i.ff] == 2){
				if (cur[x] < k){res /= 2;t=1;}
			}
			if (dis[i.ff] > res){
				dis[i.ff] = res;
				cur[i.ff] = cur[x]+t;
				q.push({i.ss, i.ff});
			}
		}
	}
	if (dis[h] == 1e18) return double(-1);
	return dis[h];
}

// int main ()
// {
// }

Subtask #1
0.0 / 5.0

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

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 2816 KB Correct.
2 Correct 24 ms 2856 KB Correct.
3 Correct 24 ms 2868 KB Correct.
4 Correct 24 ms 2880 KB Correct.
5 Correct 24 ms 2836 KB Correct.
6 Correct 77 ms 4508 KB Correct.
7 Correct 90 ms 4208 KB Correct.
8 Correct 201 ms 6172 KB Correct.
9 Correct 22 ms 2756 KB Correct.
10 Correct 21 ms 2764 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 2820 KB Correct.
2 Correct 28 ms 2852 KB Correct.
3 Correct 25 ms 2896 KB Correct.
4 Correct 24 ms 2644 KB Correct.
5 Correct 25 ms 2736 KB Correct.
6 Correct 15 ms 3936 KB Correct.

Subtask #4
0.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 860 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 3936 KB Correct.
2 Correct 36 ms 3784 KB Correct.
3 Correct 40 ms 3828 KB Correct.
4 Correct 119 ms 57908 KB Correct.
5 Correct 22 ms 2756 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 3948 KB Correct.
2 Correct 24 ms 3760 KB Correct.
3 Correct 34 ms 9004 KB Correct.
4 Correct 72 ms 59340 KB Correct.
5 Correct 26 ms 2768 KB Correct.
6 Correct 33 ms 3852 KB Correct.

Subtask #7
0.0 / 29.0

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

Subtask #8
0.0 / 3.0

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