oj.uz

Submission #918932

# Submission time Handle Problem Language Result Execution time Memory
918932 2024-01-30T21:17:40 Z tolbi Cyberland (APIO23_cyberland) C++17
100 / 100
 2869 ms 23488 KB 
#pragma optimize("Bismillahirrahmanirrahim")
#pragma GCC optimize("O3,Ofast")
#pragma target("avx2")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
template<typename X, typename Y> istream& operator>>(istream& in, pair<X,Y> &pr) {return in>>pr.first>>pr.second;}
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr) {return os<<pr.first<<" "<<pr.second;}
template<typename X, typename Y> pair<X,Y> operator+(pair<X,Y> a, pair<X,Y> b) {pair<X,Y> c; c.first=a.first+b.first,c.second=a.second+b.second;return c;}
template<typename X, typename Y> pair<X,Y> operator-(pair<X,Y> a, pair<X,Y> b) {pair<X,Y> c; c.first=a.first-b.first,c.second=a.second-b.second;return c;}
template<typename X, typename Y> void operator+=(pair<X,Y> &a, pair<X,Y> b){a.first+=b.first,a.second+=b.second;}
template<typename X, typename Y> void operator-=(pair<X,Y> &a, pair<X,Y> b){a.first-=b.first,a.second-=b.second;}
template<typename X> istream& operator>>(istream& in, vector<X> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X> ostream& operator<<(ostream& os, vector<X> arr) {for(auto &it : arr) os<<it<<" "; return os;}
template<typename X, size_t Y> istream& operator>>(istream& in, array<X,Y> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X, size_t Y> ostream& operator<<(ostream& os, array<X,Y> arr) {for(auto &it : arr) os<<it<<" "; return os;}
#define int long long
#define endl '\n'
#define vint(x) vector<int> x
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(),x.end())
#define sortrarr(x) sort(x.rbegin(),x.rend())
#define det(x) cout<<"NO\0YES"+x*3<<endl;
#define INF LONG_LONG_MAX
#define rev(x) reverse(x.begin(),x.end());
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define tol(bi) (1LL<<((int)(bi)))
const int MOD = 1e9+7;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
#include "cyberland.h"
#define ld long double
long double SIN = 1e15;
double solve(int32_t N, int32_t M, int32_t K, int32_t H, vector<int32_t> x, vector<int32_t> y, vector<int32_t> c, vector<int32_t> barr) {
	K=min(K,23*3);
	vector<vector<pair<int,int>>> arr(N);
	for (int i = 0; i < M; i++){
		arr[x[i]].push_back({y[i],c[i]});
		arr[y[i]].push_back({x[i],c[i]});
	}
	priority_queue<pair<ld,int>,vector<pair<ld,int>>,greater<pair<ld,int>>> pq;
	vector<ld> dp(N,SIN);
	vector<ld> ldp(N,SIN);
	vector<bool> pat(N,false);
	auto dfs = [&](int node, auto dfs)->void{
		pat[node]=true;
		if (node==H) return;
		for (int i = 0; i < arr[node].size(); i++){
			if (pat[arr[node][i].first]) continue;
			dfs(arr[node][i].first,dfs);
		}
	};
	dfs(0,dfs);
	pq.push({0,0});
	for (int i = 0; i < N; i++){
		if (barr[i]==0 && pat[i]){
			pq.push({0,i});
		}
	}
	auto bfs = [&](int ahmet23 = 23)->void{
		fill(dp.begin(), dp.end(), SIN);
		while (pq.size()){
			int node = pq.top().second;
			ld w = pq.top().first;
			pq.pop();
			if (dp[node]<=w) continue;
			dp[node]=w;
			if (node==H) continue;
			for (int i = 0; i < arr[node].size(); i++){
				if (dp[arr[node][i].first]<=w+arr[node][i].second) continue;
				pq.push({w+arr[node][i].second,arr[node][i].first});
			}
		}
		for (int i = 0; i < N; i++){
			if (i==H) continue;
			for (int j = 0; j < arr[i].size(); j++){
				if (barr[arr[i][j].first]!=2) continue;
				ldp[arr[i][j].first]=min(ldp[arr[i][j].first],dp[i]+arr[i][j].second);
			}
		}
	};
	for (int kal = K; kal >= 0; kal--){
		bfs();
		for (int i = 0; i < N; i++){
			if (kal && barr[i]==2){
				if (dp[i]==SIN) continue;
				if (ldp[i]==SIN) continue;
				dp[i]=min(dp[i],ldp[i]/2.0);
				ldp[i]=SIN;
			}
			pq.push({dp[i],i});
		}
	}
	bfs();
	if (dp[H]==SIN) return -1;
	return dp[H];
}

#ifdef tolbi
int32_t main() {
	int32_t T;
	assert(1 == scanf("%d", &T));
	while (T--){
		int32_t N,M,K,H;
		assert(4 == scanf("%d %d %d\n%d", &N, &M, &K, &H));
		vector<int32_t> x(M);
		vector<int32_t> y(M);
		vector<int32_t> c(M);
		vector<int32_t> arr(N);
		for (int32_t i=0;i<N;i++)
			assert(1 == scanf("%d", &arr[i]));
		for (int32_t i=0;i<M;i++)
			assert(3 == scanf("%d %d %d", &x[i], &y[i], &c[i]));
		printf("%.12lf\n", solve(N, M, K, H, x, y, c, arr));
	}
}
#endif

Compilation message

cyberland.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      | 
cyberland.cpp:3: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    3 | #pragma target("avx2")
      | 
cyberland.cpp: In lambda function:
cyberland.cpp:80:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |    for (int i = 0; i < arr[node].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~
cyberland.cpp:87:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |    for (int j = 0; j < arr[i].size(); j++){
      |                    ~~^~~~~~~~~~~~~~~
cyberland.cpp: In instantiation of 'solve(int32_t, int32_t, int32_t, int32_t, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)::<lambda(long long int, auto:23)> [with auto:23 = solve(int32_t, int32_t, int32_t, int32_t, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)::<lambda(long long int, auto:23)>]':
cyberland.cpp:64:11:   required from here
cyberland.cpp:59:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   for (int i = 0; i < arr[node].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 848 KB Correct.
2 Correct 47 ms 848 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 1368 KB Correct.
2 Correct 477 ms 1664 KB Correct.
3 Correct 455 ms 1656 KB Correct.
4 Correct 472 ms 1680 KB Correct.
5 Correct 478 ms 1860 KB Correct.
6 Correct 523 ms 3392 KB Correct.
7 Correct 695 ms 3180 KB Correct.
8 Correct 293 ms 4568 KB Correct.
9 Correct 196 ms 1360 KB Correct.
10 Correct 194 ms 1360 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 1564 KB Correct.
2 Correct 451 ms 1600 KB Correct.
3 Correct 408 ms 1852 KB Correct.
4 Correct 205 ms 1360 KB Correct.
5 Correct 202 ms 1360 KB Correct.
6 Correct 105 ms 2264 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 11980 KB Correct.
2 Correct 313 ms 1684 KB Correct.
3 Correct 291 ms 1568 KB Correct.
4 Correct 298 ms 1592 KB Correct.
5 Correct 163 ms 1360 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 1516 KB Correct.
2 Correct 381 ms 1508 KB Correct.
3 Correct 385 ms 1520 KB Correct.
4 Correct 471 ms 2976 KB Correct.
5 Correct 172 ms 1360 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 1708 KB Correct.
2 Correct 312 ms 1564 KB Correct.
3 Correct 392 ms 17856 KB Correct.
4 Correct 319 ms 2912 KB Correct.
5 Correct 178 ms 1432 KB Correct.
6 Correct 349 ms 1792 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 1676 KB Correct.
2 Correct 55 ms 856 KB Correct.
3 Correct 1258 ms 22284 KB Correct.
4 Correct 806 ms 7100 KB Correct.
5 Correct 1029 ms 16320 KB Correct.
6 Correct 721 ms 13768 KB Correct.
7 Correct 779 ms 6324 KB Correct.
8 Correct 604 ms 2752 KB Correct.
9 Correct 315 ms 1572 KB Correct.
10 Correct 326 ms 1776 KB Correct.
11 Correct 527 ms 2604 KB Correct.
12 Correct 350 ms 1556 KB Correct.
13 Correct 356 ms 1572 KB Correct.
14 Correct 659 ms 10792 KB Correct.
15 Correct 671 ms 4900 KB Correct.
16 Correct 346 ms 1612 KB Correct.
17 Correct 392 ms 1732 KB Correct.
18 Correct 380 ms 1516 KB Correct.
19 Correct 899 ms 2968 KB Correct.
20 Correct 17 ms 604 KB Correct.
21 Correct 27 ms 604 KB Correct.
22 Correct 62 ms 1624 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 781 ms 1708 KB Correct.
2 Correct 114 ms 856 KB Correct.
3 Correct 2646 ms 23488 KB Correct.
4 Correct 863 ms 3800 KB Correct.
5 Correct 2272 ms 16832 KB Correct.
6 Correct 1546 ms 13768 KB Correct.
7 Correct 1277 ms 11116 KB Correct.
8 Correct 760 ms 3020 KB Correct.
9 Correct 660 ms 1500 KB Correct.
10 Correct 672 ms 1512 KB Correct.
11 Correct 298 ms 1940 KB Correct.
12 Correct 757 ms 1908 KB Correct.
13 Correct 727 ms 1556 KB Correct.
14 Correct 2869 ms 11716 KB Correct.
15 Correct 2657 ms 11348 KB Correct.
16 Correct 1261 ms 5696 KB Correct.
17 Correct 891 ms 3308 KB Correct.
18 Correct 730 ms 1740 KB Correct.
19 Correct 815 ms 1784 KB Correct.
20 Correct 786 ms 1756 KB Correct.
21 Correct 1964 ms 2792 KB Correct.
22 Correct 32 ms 600 KB Correct.
23 Correct 54 ms 652 KB Correct.
24 Correct 130 ms 1628 KB Correct.