oj.uz

Submission #1050881

# Submission time Handle Problem Language Result Execution time Memory
1050881 2024-08-09T16:08:33 Z vjudge1 Cyberland (APIO23_cyberland) C++17
15 / 100
 36 ms 97364 KB 
#include "cyberland.h"

#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define ar array
const int N = 2e5 + 20;

namespace DSU{
	int p[N];
	void init(int n){
		iota(p, p + n + 1, 0);
	}
	int find(int x){
		if(p[x] == x)return x;
		return p[x] = find(p[x]);
	}
	bool join(int u,int v){
		u = find(u), v = find(v);
		if(u == v)return 0;
		p[u] = v;
		return 1;
	}
};
ld dist[N][100];
priority_queue<pair<ld, ar<int, 2> >, vector<pair<ld, ar<int, 2>>>, greater<pair<ld, ar<int, 2>>>> pq;

void push(int k,int x, ld d){
	if(dist[x][k] > d){
		dist[x][k] = d;
		pq.push({d, {x, k}});
	}
}

double solve(int n, int m, int K, int h, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> A) {
	vector<ar<int, 2>> g[n];;
	K = min(K, 69);
	DSU::init(n);
	for(int i = 0;i < m;i++){
		if(x[i] != h || y[i] != h)DSU::join(x[i], y[i]);
		g[x[i]].push_back({y[i], c[i]});
		g[y[i]].push_back({x[i], c[i]});
	}
	ld pow[K + 1];
	pow[0] = 1;
	for(int i = 1;i <= K;i++)pow[i] = pow[i - 1] / 2;
	A[0] = 0;
	pq = priority_queue<pair<ld, ar<int, 2> >, vector<pair<ld, ar<int, 2>>>, greater<pair<ld, ar<int, 2>>>>();
	for(int i = 0;i < n;i++){
		for(int j = 0;j <= K;j++){
			dist[i][j] = 1e18;
		}
	}
	push(K, h, 0);
	while(pq.size()){
		ld d = pq.top().first;
		auto [x, k] = pq.top().second;
		pq.pop();
		if(dist[x][k] < d)continue;
		if(A[x] == 0)return d;
		for(auto [u, c]: g[x]){
			if(DSU::find(u) != DSU::find(0))continue;
			push(k, u, d + c * pow[K - k]);
			if(A[x] == 2 && k > 0)push(k - 1, u, d + c * pow[K - k + 1]);
		}
	}
    return -1;
}

Subtask #1
0.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2648 KB Correct.
2 Correct 21 ms 2772 KB Correct.
3 Correct 20 ms 2904 KB Correct.
4 Correct 21 ms 2652 KB Correct.
5 Correct 25 ms 2652 KB Correct.
6 Correct 17 ms 17756 KB Correct.
7 Correct 22 ms 17748 KB Correct.
8 Correct 11 ms 33112 KB Correct.
9 Correct 20 ms 600 KB Correct.
10 Correct 20 ms 856 KB Correct.

Subtask #3
0.0 / 13.0

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

Subtask #4
0.0 / 19.0

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

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2648 KB Correct.
2 Correct 24 ms 2648 KB Correct.
3 Correct 22 ms 2648 KB Correct.
4 Correct 28 ms 17928 KB Correct.
5 Correct 20 ms 660 KB Correct.

Subtask #6
0.0 / 16.0

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

Subtask #7
0.0 / 29.0

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

Subtask #8
0.0 / 3.0

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