oj.uz

답안 #228916

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
228916 2020-05-03T05:41:51 Z alishahali1382 Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 123 ms 154360 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int SQ=180, MAXN=180*30000;

int n, m, k, u, v, x, y, t, a, b, ans;
int B[MAXN], P[MAXN];
int dist[MAXN];
bool mark[MAXN];
vector<pii> G[MAXN];
priority_queue<pii, vector<pii>, greater<pii>> pq;

inline void addedge(int v1, int j1, int v2, int j2, int w){
	G[v1*SQ+j1].pb({v2*SQ+j2, w});
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	memset(dist, 63, sizeof(dist));
	cin>>n>>m;
	for (int i=0; i<n; i++) for (int j=1; j<SQ; j++){
		if (i>=j) addedge(i, j, i-j, j, 1);
		if (i+j<n) addedge(i, j, i+j, j, 1);
		addedge(i, j, i, 0, 0);
	}
	for (int i=0; i<m; i++){
		cin>>B[i]>>P[i];
		if (P[i]<SQ) G[B[i]*SQ].pb({B[i]*SQ+P[i], 0});
		else{
			for (int j=1; B[i]-j*SQ>=0; j++) G[B[i]*SQ].pb({(B[i]-j*SQ)*SQ, j});
			for (int j=1; B[i]+j*SQ<n; j++) G[B[i]*SQ].pb({(B[i]+j*SQ)*SQ, j});
		}
	}
	
	pq.push({dist[B[0]*SQ]=0, B[0]*SQ});
	while (pq.size()){
		int v=pq.top().second;
		pq.pop();
		if (mark[v]) continue ;
		mark[v]=1;
		for (pii p:G[v]) if (dist[p.first]>dist[v]+p.second)
			pq.push({dist[p.first]=dist[v]+p.second, p.first});
	
	}
	
	ans=dist[SQ*B[1]];
	if (ans>=inf) ans=-1;
	cout<<ans<<'\n';
	
	return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 148344 KB Output is correct
2 Correct 86 ms 148216 KB Output is correct
3 Correct 89 ms 148344 KB Output is correct
4 Correct 86 ms 148344 KB Output is correct
5 Correct 85 ms 148344 KB Output is correct
6 Correct 86 ms 148344 KB Output is correct
7 Correct 85 ms 148344 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 148380 KB Output is correct
2 Correct 88 ms 148292 KB Output is correct
3 Correct 89 ms 148344 KB Output is correct
4 Correct 87 ms 148384 KB Output is correct
5 Correct 90 ms 148344 KB Output is correct
6 Correct 91 ms 148344 KB Output is correct
7 Correct 90 ms 148412 KB Output is correct
8 Correct 88 ms 148472 KB Output is correct
9 Correct 91 ms 148608 KB Output is correct
10 Correct 93 ms 148984 KB Output is correct
11 Correct 94 ms 148984 KB Output is correct
12 Correct 92 ms 148988 KB Output is correct
13 Correct 91 ms 148988 KB Output is correct
14 Correct 94 ms 148984 KB Output is correct
15 Correct 94 ms 149104 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 148344 KB Output is correct
2 Correct 92 ms 148300 KB Output is correct
3 Correct 89 ms 148344 KB Output is correct
4 Correct 92 ms 148344 KB Output is correct
5 Correct 92 ms 148524 KB Output is correct
6 Correct 92 ms 148344 KB Output is correct
7 Correct 90 ms 148344 KB Output is correct
8 Correct 92 ms 148600 KB Output is correct
9 Correct 91 ms 148728 KB Output is correct
10 Correct 105 ms 148984 KB Output is correct
11 Correct 95 ms 148984 KB Output is correct
12 Correct 97 ms 148984 KB Output is correct
13 Correct 96 ms 148992 KB Output is correct
14 Correct 93 ms 149112 KB Output is correct
15 Correct 92 ms 148984 KB Output is correct
16 Correct 95 ms 149624 KB Output is correct
17 Incorrect 123 ms 154208 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 148316 KB Output is correct
2 Correct 95 ms 148344 KB Output is correct
3 Correct 93 ms 148344 KB Output is correct
4 Correct 91 ms 148344 KB Output is correct
5 Correct 89 ms 148344 KB Output is correct
6 Correct 88 ms 148344 KB Output is correct
7 Correct 89 ms 148344 KB Output is correct
8 Correct 93 ms 148472 KB Output is correct
9 Correct 92 ms 148664 KB Output is correct
10 Correct 91 ms 148984 KB Output is correct
11 Correct 93 ms 148984 KB Output is correct
12 Correct 93 ms 148984 KB Output is correct
13 Correct 92 ms 148984 KB Output is correct
14 Correct 92 ms 148984 KB Output is correct
15 Correct 96 ms 148984 KB Output is correct
16 Correct 93 ms 149624 KB Output is correct
17 Incorrect 112 ms 154360 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 148476 KB Output is correct
2 Correct 89 ms 148348 KB Output is correct
3 Correct 90 ms 148344 KB Output is correct
4 Correct 92 ms 148344 KB Output is correct
5 Correct 89 ms 148344 KB Output is correct
6 Correct 90 ms 148344 KB Output is correct
7 Correct 90 ms 148344 KB Output is correct
8 Correct 89 ms 148472 KB Output is correct
9 Correct 90 ms 148604 KB Output is correct
10 Correct 91 ms 148984 KB Output is correct
11 Correct 90 ms 148984 KB Output is correct
12 Correct 88 ms 148984 KB Output is correct
13 Correct 93 ms 148984 KB Output is correct
14 Correct 93 ms 148984 KB Output is correct
15 Correct 95 ms 148984 KB Output is correct
16 Correct 92 ms 149624 KB Output is correct
17 Incorrect 116 ms 154360 KB Output isn't correct
18 Halted 0 ms 0 KB -