제출 #1278122

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278122		herominhsteve	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	534 ms	8956 KiB

skyscraper

#include <bits/stdc++.h>
#define el '\n'
#define FNAME "APIO15_skyscraper"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9 + 7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}

void setup(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	if (fopen(FNAME".inp","r")){
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

const int MAXN = 30'005;
const int INF = 1e9 + 15092007;

int n,m;
vector<int> jump[MAXN];
int doge0Pos,doge1Pos;

void init(){
	cin>>n>>m;
	for (int i=0;i<m;i++){
		int pos,p;
		cin>>pos>>p;
		if (i!=1) jump[pos].push_back(p);
		if (!i) doge0Pos = pos;
		if (i==1) doge1Pos = pos;
	}	
	for (int i=0;i<n;i++){
		sort(allof(jump[i]));
		jump[i].resize(unique(allof(jump[i]))-jump[i].begin());
	}
}

struct Edges{
	int v;
	long long w;
	Edges(): v(0),w(0) {}
	Edges(int V,long long W):v(V),w(W) {}
	bool operator < (const Edges &other) const{
		return w>other.w;
	}
};

int Dijkstra(){
	vector<int> distancia(n+1,INF);
	distancia[doge0Pos] = 0;
	priority_queue<Edges> pq;
	pq.emplace(doge0Pos,0);

	while (!pq.empty()){
		int u = pq.top().v;
		int dis = pq.top().w;
		pq.pop();
		if (u == doge1Pos){
			return dis;
		}
		if (dis > distancia[u]) continue;
		for (int p : jump[u]){
			for (int v = u + p, cnt = 1; v < n; v+=p, cnt++){
				if (minimize(distancia[v],dis + cnt)){
					pq.emplace(v,distancia[v]);
				}
			}
			for (int v = u - p, cnt = 1; v >= 0; v-=p, cnt++){
				if (minimize(distancia[v],dis + cnt)){
					pq.emplace(v,distancia[v]);
				}
			}
		}
	}
	return -1;
}

void sol(){
	cout<<Dijkstra();
}

int main(){
    setup();
    init();
    sol();
}

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

skyscraper.cpp: In function 'void setup()':
skyscraper.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |                 freopen(FNAME".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 freopen(FNAME".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 43 / 43