oj.uz

Submission #759968

# Submission time Handle Problem Language Result Execution time Memory
759968 2023-06-17T06:14:03 Z OrazB Cyberland (APIO23_cyberland) C++17
100 / 100
 1479 ms 73412 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

int vis[N];
set<pii> q[N];
vector<pair<int,int>> E[N];
vector<int> z;

void dfs(int nd, int h){
	vis[nd] = 1;
	for (auto i : E[nd]){
		if (i.ff == h or vis[i.ff]) continue;
		dfs(i.ff, h);	
	}
}

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 < max(70,n); i++){
		vis[i] = 0;
		E[i].clear();
		if (i <= 70) q[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]});	
	}
	z.clear();
	z.pb(0);
	vector<vector<double>> dis(min(73,k+2), vector<double>(n+1, 1e15));	
	dfs(0, h);
	for (int i = 0; i < n; i++) if (!arr[i] and vis[i]) z.pb(i);
	double ans = 1e15;
	for (auto i : z){
		dis[0][i] = 0;
		q[0].insert({0, i});
	}
	for (int i = 0; i <= min(k,70); i++){
		while(!q[i].empty()){
			int x = (*q[i].begin()).ss;
			q[i].erase(q[i].begin());
			if (x == h) continue;
			for (auto j : E[x]){
				double res = dis[i][x]+j.ss;
				if (dis[i][j.ff] > res){
					dis[i][j.ff] = res;
					q[i].insert({dis[i][j.ff], j.ff});
				}
				if (arr[j.ff] == 2){	
					res /= 2;
					if (dis[i+1][j.ff] > res){
						dis[i+1][j.ff] = res;
						q[i+1].insert({dis[i+1][j.ff], j.ff});
					}
				}
			}
		}
		ans = min(ans, dis[i][h]);
	}
	if (ans == 1e15) return double(-1);
	return ans;
}

// 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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 7424 KB Correct.
2 Correct 36 ms 7508 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 7784 KB Correct.
2 Correct 33 ms 7720 KB Correct.
3 Correct 27 ms 7768 KB Correct.
4 Correct 28 ms 7752 KB Correct.
5 Correct 30 ms 7768 KB Correct.
6 Correct 26 ms 10616 KB Correct.
7 Correct 34 ms 10612 KB Correct.
8 Correct 20 ms 13924 KB Correct.
9 Correct 28 ms 7544 KB Correct.
10 Correct 27 ms 7552 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 7764 KB Correct.
2 Correct 31 ms 7764 KB Correct.
3 Correct 26 ms 7772 KB Correct.
4 Correct 34 ms 7560 KB Correct.
5 Correct 29 ms 7500 KB Correct.
6 Correct 10 ms 10196 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 26696 KB Correct.
2 Correct 129 ms 7760 KB Correct.
3 Correct 122 ms 7804 KB Correct.
4 Correct 127 ms 7772 KB Correct.
5 Correct 83 ms 7536 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 7784 KB Correct.
2 Correct 27 ms 7792 KB Correct.
3 Correct 32 ms 7808 KB Correct.
4 Correct 25 ms 10520 KB Correct.
5 Correct 22 ms 7544 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 7816 KB Correct.
2 Correct 26 ms 7832 KB Correct.
3 Correct 46 ms 32268 KB Correct.
4 Correct 21 ms 9628 KB Correct.
5 Correct 25 ms 7552 KB Correct.
6 Correct 24 ms 7832 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 7832 KB Correct.
2 Correct 32 ms 7764 KB Correct.
3 Correct 602 ms 29132 KB Correct.
4 Correct 334 ms 13072 KB Correct.
5 Correct 709 ms 24272 KB Correct.
6 Correct 372 ms 15572 KB Correct.
7 Correct 313 ms 13004 KB Correct.
8 Correct 267 ms 8460 KB Correct.
9 Correct 128 ms 7864 KB Correct.
10 Correct 124 ms 7828 KB Correct.
11 Correct 215 ms 7860 KB Correct.
12 Correct 155 ms 7816 KB Correct.
13 Correct 139 ms 7840 KB Correct.
14 Correct 290 ms 14152 KB Correct.
15 Correct 276 ms 9744 KB Correct.
16 Correct 146 ms 7924 KB Correct.
17 Correct 160 ms 7856 KB Correct.
18 Correct 159 ms 7836 KB Correct.
19 Correct 407 ms 7748 KB Correct.
20 Correct 11 ms 7632 KB Correct.
21 Correct 13 ms 7676 KB Correct.
22 Correct 28 ms 8148 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 8696 KB Correct.
2 Correct 55 ms 8404 KB Correct.
3 Correct 315 ms 73412 KB Correct.
4 Correct 353 ms 10112 KB Correct.
5 Correct 1479 ms 35880 KB Correct.
6 Correct 767 ms 18760 KB Correct.
7 Correct 586 ms 19732 KB Correct.
8 Correct 329 ms 8444 KB Correct.
9 Correct 260 ms 8588 KB Correct.
10 Correct 244 ms 8488 KB Correct.
11 Correct 255 ms 7524 KB Correct.
12 Correct 280 ms 8620 KB Correct.
13 Correct 276 ms 8552 KB Correct.
14 Correct 1455 ms 34448 KB Correct.
15 Correct 1030 ms 39688 KB Correct.
16 Correct 515 ms 18300 KB Correct.
17 Correct 340 ms 9892 KB Correct.
18 Correct 269 ms 8580 KB Correct.
19 Correct 314 ms 8760 KB Correct.
20 Correct 303 ms 8752 KB Correct.
21 Correct 897 ms 9820 KB Correct.
22 Correct 18 ms 7508 KB Correct.
23 Correct 23 ms 8040 KB Correct.
24 Correct 56 ms 8440 KB Correct.