oj.uz

답안 #208783

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
208783 2020-03-12T07:44:59 Z YJU Jakarta Skyscrapers (APIO15_skyscraper) C++14
36 / 100
 1000 ms 262148 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll MOD=1e9+7;
const ll N=3e4+5;
const ll INF=(1LL<<60);
const ld pi=3.14159265359;
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()
 
 
ll n,m,b[N],p[N],x,y,dis[N];
vector<ll> P[N],tmp;
vector<pll> v[N];
vector<vector<ll> > lis;
priority_queue<pll,vector<pll>,greater<pll> > pq;
 
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;
	REP(i,m){
		cin>>b[i]>>p[i];
		P[p[i]].pb(b[i]);
	}
	for(ll step=1;step<N;++step){
		if(!SZ(P[step]))continue;
		lis.clear();lis.resize(step);
		tmp.clear();
		for(auto i:P[step]){
			lis[i%step].pb(i);
			tmp.pb(i%step);
		}
		sort(tmp.begin(),tmp.end());
		tmp.resize(unique(tmp.begin(),tmp.end())-tmp.begin());
		for(auto i:tmp){
			for(ll j=1;j<SZ(lis[i]);++j){
				x=lis[i][j-1],y=lis[i][j];
				for(ll ii=x;ii<=y;ii+=step){
					v[x].pb(mp(ii,(ii-x)/step));
					v[y].pb(mp(ii,(y-ii)/step));
				}
			}
			for(ll ii=lis[i].back();ii<N;ii+=step)x=lis[i].back(),v[x].pb(mp(ii,(ii-x)/step));
			for(ll ii=lis[i][0];ii>=0;ii-=step)x=lis[i][0],v[x].pb(mp(ii,(x-ii)/step));
		}
	}
	REP(i,N)dis[i]=INF;
	pq.push(mp(0,b[0]));
	while(SZ(pq)){
		x=pq.top().Y;y=pq.top().X;pq.pop();
		if(dis[x]<=y)continue;
		dis[x]=y;
		for(auto j:v[x])if(dis[j.X]>dis[x]+j.Y)pq.push(mp(dis[x]+j.Y,j.X));
	}
	cout<<(dis[b[1]]==INF?-1:dis[b[1]])<<"\n";
	return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 4212 KB Output is correct
2 Correct 10 ms 3188 KB Output is correct
3 Correct 7 ms 2552 KB Output is correct
4 Correct 6 ms 2296 KB Output is correct
5 Correct 12 ms 4340 KB Output is correct
6 Correct 14 ms 4084 KB Output is correct
7 Correct 11 ms 3188 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 4212 KB Output is correct
2 Correct 10 ms 3320 KB Output is correct
3 Correct 7 ms 2552 KB Output is correct
4 Correct 6 ms 2296 KB Output is correct
5 Correct 13 ms 4344 KB Output is correct
6 Correct 14 ms 4080 KB Output is correct
7 Correct 9 ms 3184 KB Output is correct
8 Correct 13 ms 3968 KB Output is correct
9 Correct 30 ms 6160 KB Output is correct
10 Correct 114 ms 18788 KB Output is correct
11 Correct 395 ms 60352 KB Output is correct
12 Correct 22 ms 5800 KB Output is correct
13 Correct 11 ms 3816 KB Output is correct
14 Correct 546 ms 68536 KB Output is correct
15 Correct 544 ms 68796 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 4212 KB Output is correct
2 Correct 9 ms 3188 KB Output is correct
3 Correct 7 ms 2552 KB Output is correct
4 Correct 7 ms 2296 KB Output is correct
5 Correct 13 ms 4336 KB Output is correct
6 Correct 14 ms 4084 KB Output is correct
7 Correct 9 ms 3188 KB Output is correct
8 Correct 14 ms 3964 KB Output is correct
9 Correct 29 ms 6160 KB Output is correct
10 Correct 116 ms 18788 KB Output is correct
11 Correct 370 ms 60352 KB Output is correct
12 Correct 21 ms 5800 KB Output is correct
13 Correct 11 ms 3820 KB Output is correct
14 Correct 551 ms 68540 KB Output is correct
15 Correct 559 ms 68796 KB Output is correct
16 Correct 18 ms 12664 KB Output is correct
17 Correct 160 ms 29796 KB Output is correct
18 Correct 11 ms 4476 KB Output is correct
19 Correct 9 ms 3572 KB Output is correct
20 Correct 169 ms 37796 KB Output is correct
21 Correct 12 ms 5108 KB Output is correct
22 Correct 10 ms 4084 KB Output is correct
23 Correct 29 ms 6748 KB Output is correct
24 Correct 50 ms 10536 KB Output is correct
25 Correct 24 ms 5228 KB Output is correct
26 Correct 25 ms 6408 KB Output is correct
27 Correct 23 ms 5484 KB Output is correct
28 Correct 20 ms 8948 KB Output is correct
29 Correct 255 ms 35496 KB Output is correct
30 Correct 59 ms 11752 KB Output is correct
31 Correct 125 ms 19492 KB Output is correct
32 Correct 88 ms 16512 KB Output is correct
33 Correct 549 ms 67976 KB Output is correct
34 Correct 557 ms 68136 KB Output is correct

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 4212 KB Output is correct
2 Correct 9 ms 3188 KB Output is correct
3 Correct 7 ms 2552 KB Output is correct
4 Correct 6 ms 2296 KB Output is correct
5 Correct 13 ms 4336 KB Output is correct
6 Correct 14 ms 4084 KB Output is correct
7 Correct 9 ms 3188 KB Output is correct
8 Correct 14 ms 3960 KB Output is correct
9 Correct 29 ms 6156 KB Output is correct
10 Correct 113 ms 19048 KB Output is correct
11 Correct 370 ms 60352 KB Output is correct
12 Correct 21 ms 5800 KB Output is correct
13 Correct 11 ms 3816 KB Output is correct
14 Correct 550 ms 68724 KB Output is correct
15 Correct 550 ms 68792 KB Output is correct
16 Correct 18 ms 12664 KB Output is correct
17 Correct 162 ms 29792 KB Output is correct
18 Correct 11 ms 4600 KB Output is correct
19 Correct 9 ms 3568 KB Output is correct
20 Correct 177 ms 37796 KB Output is correct
21 Correct 12 ms 5108 KB Output is correct
22 Correct 10 ms 4084 KB Output is correct
23 Correct 28 ms 6832 KB Output is correct
24 Correct 49 ms 10536 KB Output is correct
25 Correct 24 ms 5228 KB Output is correct
26 Correct 25 ms 6408 KB Output is correct
27 Correct 21 ms 5480 KB Output is correct
28 Correct 21 ms 8948 KB Output is correct
29 Correct 260 ms 35516 KB Output is correct
30 Correct 60 ms 11752 KB Output is correct
31 Correct 122 ms 19488 KB Output is correct
32 Correct 87 ms 16576 KB Output is correct
33 Correct 542 ms 68008 KB Output is correct
34 Correct 558 ms 68128 KB Output is correct
35 Correct 726 ms 79124 KB Output is correct
36 Correct 132 ms 20476 KB Output is correct
37 Correct 979 ms 121332 KB Output is correct
38 Correct 854 ms 119624 KB Output is correct
39 Correct 858 ms 119412 KB Output is correct
40 Correct 881 ms 119292 KB Output is correct
41 Correct 882 ms 119748 KB Output is correct
42 Correct 55 ms 8956 KB Output is correct
43 Correct 30 ms 7804 KB Output is correct
44 Correct 546 ms 101308 KB Output is correct
45 Runtime error 369 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
46 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 4212 KB Output is correct
2 Correct 9 ms 3312 KB Output is correct
3 Correct 7 ms 2548 KB Output is correct
4 Correct 7 ms 2296 KB Output is correct
5 Correct 13 ms 4340 KB Output is correct
6 Correct 15 ms 4084 KB Output is correct
7 Correct 10 ms 3192 KB Output is correct
8 Correct 14 ms 3964 KB Output is correct
9 Correct 29 ms 6160 KB Output is correct
10 Correct 112 ms 18792 KB Output is correct
11 Correct 389 ms 60352 KB Output is correct
12 Correct 22 ms 5800 KB Output is correct
13 Correct 12 ms 3820 KB Output is correct
14 Correct 570 ms 68668 KB Output is correct
15 Correct 568 ms 68796 KB Output is correct
16 Correct 18 ms 12664 KB Output is correct
17 Correct 163 ms 29792 KB Output is correct
18 Correct 11 ms 4472 KB Output is correct
19 Correct 9 ms 3572 KB Output is correct
20 Correct 179 ms 37792 KB Output is correct
21 Correct 12 ms 4976 KB Output is correct
22 Correct 11 ms 4080 KB Output is correct
23 Correct 32 ms 6828 KB Output is correct
24 Correct 49 ms 10536 KB Output is correct
25 Correct 25 ms 5232 KB Output is correct
26 Correct 25 ms 6408 KB Output is correct
27 Correct 23 ms 5488 KB Output is correct
28 Correct 21 ms 8948 KB Output is correct
29 Correct 263 ms 35512 KB Output is correct
30 Correct 63 ms 11756 KB Output is correct
31 Correct 127 ms 19492 KB Output is correct
32 Correct 85 ms 16512 KB Output is correct
33 Correct 561 ms 67880 KB Output is correct
34 Correct 595 ms 68264 KB Output is correct
35 Correct 738 ms 79252 KB Output is correct
36 Correct 126 ms 20476 KB Output is correct
37 Execution timed out 1016 ms 121452 KB Time limit exceeded
38 Halted 0 ms 0 KB -