Submission #918932

#	Time	Username	Problem	Language	Result	Execution time	Memory
918932		tolbi	Cyberland (APIO23_cyberland)	C++17	100 / 100	2869 ms	23488 KiB

cyberland

#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 (stderr)

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 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 29 / 29
• Subtask 8: 3 / 3