제출 #922388

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
922388		dozer	사이버랜드 (APIO23_cyberland)	C++17	97 / 100	3071 ms	85456 KiB

cyberland

#include "cyberland.h"
#pragma GCC optimize("O3")
#pragma optimize("avx2")
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define fileio() freopen("curling.in", "r", stdin), freopen("curling.out", "w", stdout)

const double INF = 2e18 + 7;


struct cmp{
	bool operator()(pair<long double, int> a, pair<long double, int> b){
		return a.st < b.st;
	}
};

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
	int lim = min(K, 70);
	vector<vector<double>> dist(lim + 5, vector<double>(N, INF));
	vector<pii> adj[N + 5];
	for (int i = 0; i < M; i++){
		adj[x[i]].pb({y[i], c[i]});
		adj[y[i]].pb({x[i], c[i]});
	}
	vector<int> mark(N + 5, 0);
	queue<int> q;
	q.push(0);
	mark[0] = 1;
	while(!q.empty()){
		int top = q.front();
		q.pop();
		for (auto i : adj[top]){
			if (mark[i.st] == 0){
				mark[i.st] = 1;
				if (i.st != H) q.push(i.st);
			}
		}
	}

	dist[0][H] = 0;
	double mini = INF;
	for (int i = 0; i <= lim; i++){
		priority_queue<pair<double, int>, vector<pair<double, int>>, cmp> q;
		for (int j = 0; j < N; j++){
			if (i == 0 || j != H) q.push({-dist[i][j], j});
		}
		double pre1 = (1LL<<i), pre2 = (1LL<<(i + 1));

		
		while(!q.empty()){
			int top = q.top().nd;
			q.pop();
			int curr = i;
			if (arr[top] != 2 || i == lim){
				for (auto j : adj[top]){
					int v = j.st, w = j.nd;
					double upd = dist[i][top] + (double)w / pre1;
					if (dist[i][v] > upd){
						dist[i][v] = upd;
						if (v != H) q.push({-upd, v});
					}
				}
			}
				
			else if (arr[top] == 2) {
				for (auto j : adj[top]){
					int v = j.st, w = j.nd;
					double upd = dist[i][top] + (double)w / pre2;
					if (dist[i + 1][v] > upd){
						dist[i + 1][v] = upd;
					}
				}	
			}
		}
		for (int j = 0; j < N; j++){
			if (mark[j] && arr[j] == 0) mini = min(mini, dist[i][j]);		
		}
		mini = min(mini, dist[i][0]);
	}
		
	if (mini > 1e18) return -1;
	return mini;
}

컴파일 시 표준 에러 (stderr) 메시지

cyberland.cpp:3: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    3 | #pragma optimize("avx2")
      | 
cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:58:8: warning: unused variable 'curr' [-Wunused-variable]
   58 |    int curr = 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: 0 / 3