oj.uz

Submission #758814

# Submission time Handle Problem Language Result Execution time Memory
758814 2023-06-15T10:47:03 Z OrazB Cyberland (APIO23_cyberland) C++17
44 / 100
 3000 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 <double, int>
#define pb push_back
#define ff first
#define ss second

vector<pii> E[N];

double F(int x){
	double res = 1.0;
	while(x--) res *= 2;
	return res;
}

void dfs(int nd, int h, vector<int> arr, vector<int> &z, vector<double> &dis, vector<bool> &vis){
	if (!arr[nd]){
		z.pb(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, z, 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<int> vec, z = {0};
	vector<bool> vis(n, 0);
	vector<double> dis(n, 1e15);
	dis[0] = 0;
	dfs(0, h, arr, z, dis, vis);
	for (int i = 0; i < n; i++){
		if (arr[i] == 2) vec.pb(i);
	}
	set<pii> q;
	for (auto i : z) q.insert({0, i});
	for (int i = 0; i <= k; i++){
		vector<bool> chk(n, 0);
		while(!q.empty()){
			int x = (*q.begin()).ss;
			q.erase(q.begin());
			if (x == h or chk[x]) continue;
			chk[x] = 1;
			for (auto j : E[x]){
				double res = (dis[x]/F(i))+j.ss;
				if (dis[j.ff] > res){
					q.erase({dis[j.ff], j.ff});
					dis[j.ff] = res;
					q.insert({dis[j.ff], j.ff});
				}
			}
		}
		for (auto j : z) q.insert({0, j});
		for (auto j : vec) q.insert({dis[j], j});
	}
	if (dis[h] == 1e15) return double(-1);
	return dis[h];
}

// int main () 
// {
// 	int n, m, k, h;
// 	cin >> n >> m >> k >> h;
// 	vector<int> x(m), y(m), c(m), arr(n);
// 	for (int i = 0; i < m; i++){
// 		cin >> x[i] >> y[i] >> c[i];
// 	}
// 	for (int i = 0; i < n; i++) cin >> arr[i];
// 	cout << solve(n,m,k,h,x,y,c,arr);
// }

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 2768 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2916 KB Correct.
2 Correct 28 ms 2852 KB Correct.
3 Correct 40 ms 2884 KB Correct.
4 Correct 27 ms 2904 KB Correct.
5 Correct 27 ms 2936 KB Correct.
6 Correct 78 ms 4352 KB Correct.
7 Correct 93 ms 4300 KB Correct.
8 Correct 218 ms 6028 KB Correct.
9 Correct 30 ms 2644 KB Correct.
10 Correct 26 ms 2748 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 2844 KB Correct.
2 Correct 117 ms 2852 KB Correct.
3 Correct 104 ms 2948 KB Correct.
4 Correct 106 ms 2732 KB Correct.
5 Correct 115 ms 2732 KB Correct.
6 Correct 45 ms 4072 KB Correct.

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 696 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3940 KB Correct.
2 Correct 28 ms 3884 KB Correct.
3 Correct 32 ms 3912 KB Correct.
4 Correct 121 ms 58128 KB Correct.
5 Correct 29 ms 2772 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 4024 KB Correct.
2 Correct 56 ms 3888 KB Correct.
3 Correct 32 ms 10028 KB Correct.
4 Correct 99 ms 59660 KB Correct.
5 Correct 60 ms 2644 KB Correct.
6 Correct 81 ms 3912 KB Correct.

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 181 ms 3892 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3074 ms 2644 KB Time limit exceeded
2 Halted 0 ms 0 KB -