oj.uz

답안 #969819

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
969819 2024-04-25T16:00:32 Z pcc Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 141 ms 197540 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC target("avx2,popcnt,sse4")
#pragma GCC optimize("O3,unroll-loops")
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int inf = 1e9;
const int mxn = 3e4+10;
const int mxe = mxn*sqrt(mxn)*3;
const int mxv = mxe;

map<pii,vector<int>> mp;
int N,M;
int ecnt,vcnt;
int to[mxe],nid[mxe];
bitset<mxv> wei;
int head[mxv];
int dist[mxv];
int S,T;
int ts;

void add_edge(int a,int b,int w){
	ecnt++;
	nid[ecnt] = head[a];
	to[ecnt] = b;
	wei[ecnt] = w;
	head[a] = ecnt;
}

bitset<mxv> done;
deque<int> dq;

void BFS(){
	dq.resize(mxv*2);
	fill(dist,dist+mxv,inf);
	dist[S] = 0;
	dq.push_back(S);
	while(!dq.empty()){
		int now = dq.front();
		dq.pop_front();
		if(done[now])continue;
		done[now] = true;
		if(now == T)break;
		for(int eid = head[now];eid;eid = nid[eid]){
			int nxt = to[eid],w = wei[eid];
			//cout<<now<<' '<<nxt<<":"<<dist[now]+w<<' '<<dist[nxt]<<endl;
			if(!w){
				if(dist[nxt]>dist[now]){
					dist[nxt] = dist[now];
					dq.push_front(nxt);
				}
			}
			else{
				if(dist[nxt]>dist[now]+w){
					dist[nxt] = dist[now]+w;
					dq.push_back(nxt);
				}
			}
		}
	}
	return;
}


int main(){
	ts = clock();
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M;
	for(int i = 0;i<M;i++){
		pii tmp;
		cin>>tmp.fs>>tmp.sc;
		mp[pii(tmp.sc,tmp.fs%tmp.sc)].push_back(tmp.fs);
		if(!i)S = tmp.fs;
		if(i == 1)T = tmp.fs;
	}
	vcnt = N-1;
	for(auto &i:mp){
		sort(i.sc.rbegin(),i.sc.rend());
		for(int j = i.fs.sc;j<N;j+=i.fs.fs){
			vcnt++;
			add_edge(vcnt,j,0);
			while(!i.sc.empty()&&i.sc.back() == j){
				add_edge(i.sc.back(),vcnt,0);
				i.sc.pop_back();
			}
			if(j != i.fs.sc){
				add_edge(vcnt-1,vcnt,1);
				add_edge(vcnt,vcnt-1,1);
			}
		}
	}
	BFS();
	cout<<(dist[T]>=inf?-1:dist[T])<<'\n';
	return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 132 ms 197200 KB Output is correct
2 Correct 76 ms 197112 KB Output is correct
3 Correct 75 ms 197204 KB Output is correct
4 Correct 119 ms 196948 KB Output is correct
5 Correct 116 ms 196944 KB Output is correct
6 Correct 137 ms 197188 KB Output is correct
7 Correct 121 ms 197252 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 197204 KB Output is correct
2 Correct 77 ms 196944 KB Output is correct
3 Correct 78 ms 196944 KB Output is correct
4 Correct 116 ms 197144 KB Output is correct
5 Correct 122 ms 197144 KB Output is correct
6 Correct 116 ms 197200 KB Output is correct
7 Correct 134 ms 196944 KB Output is correct
8 Correct 120 ms 197052 KB Output is correct
9 Correct 115 ms 196956 KB Output is correct
10 Correct 117 ms 197208 KB Output is correct
11 Correct 118 ms 197128 KB Output is correct
12 Correct 120 ms 197420 KB Output is correct
13 Correct 126 ms 197204 KB Output is correct
14 Correct 121 ms 197328 KB Output is correct
15 Correct 119 ms 197344 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 122 ms 197140 KB Output is correct
2 Correct 81 ms 196948 KB Output is correct
3 Correct 77 ms 196948 KB Output is correct
4 Correct 118 ms 196944 KB Output is correct
5 Correct 125 ms 196948 KB Output is correct
6 Correct 116 ms 197084 KB Output is correct
7 Correct 115 ms 197196 KB Output is correct
8 Correct 117 ms 196944 KB Output is correct
9 Correct 135 ms 197152 KB Output is correct
10 Correct 117 ms 197204 KB Output is correct
11 Correct 124 ms 197332 KB Output is correct
12 Correct 121 ms 197176 KB Output is correct
13 Correct 124 ms 197204 KB Output is correct
14 Correct 118 ms 197260 KB Output is correct
15 Correct 118 ms 197388 KB Output is correct
16 Correct 118 ms 197252 KB Output is correct
17 Correct 132 ms 197196 KB Output is correct
18 Correct 117 ms 197196 KB Output is correct
19 Correct 128 ms 197236 KB Output is correct
20 Correct 115 ms 197200 KB Output is correct
21 Correct 118 ms 197204 KB Output is correct
22 Correct 117 ms 197204 KB Output is correct
23 Correct 118 ms 197196 KB Output is correct
24 Correct 121 ms 197540 KB Output is correct
25 Correct 116 ms 197204 KB Output is correct
26 Correct 116 ms 197204 KB Output is correct
27 Correct 116 ms 197200 KB Output is correct
28 Incorrect 85 ms 197532 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 197052 KB Output is correct
2 Correct 76 ms 196948 KB Output is correct
3 Correct 76 ms 196996 KB Output is correct
4 Correct 119 ms 197204 KB Output is correct
5 Correct 116 ms 197200 KB Output is correct
6 Correct 115 ms 196948 KB Output is correct
7 Correct 130 ms 197048 KB Output is correct
8 Correct 118 ms 196952 KB Output is correct
9 Correct 116 ms 196944 KB Output is correct
10 Correct 115 ms 197208 KB Output is correct
11 Correct 117 ms 197204 KB Output is correct
12 Correct 116 ms 197200 KB Output is correct
13 Correct 117 ms 196992 KB Output is correct
14 Correct 127 ms 197204 KB Output is correct
15 Correct 117 ms 197200 KB Output is correct
16 Correct 115 ms 197280 KB Output is correct
17 Correct 117 ms 197204 KB Output is correct
18 Correct 117 ms 197340 KB Output is correct
19 Correct 116 ms 197280 KB Output is correct
20 Correct 116 ms 197204 KB Output is correct
21 Correct 117 ms 197336 KB Output is correct
22 Correct 119 ms 197284 KB Output is correct
23 Correct 116 ms 197332 KB Output is correct
24 Correct 117 ms 197296 KB Output is correct
25 Correct 120 ms 197200 KB Output is correct
26 Correct 118 ms 197204 KB Output is correct
27 Correct 121 ms 197108 KB Output is correct
28 Incorrect 75 ms 197516 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 119 ms 197152 KB Output is correct
2 Correct 77 ms 196948 KB Output is correct
3 Correct 80 ms 196948 KB Output is correct
4 Correct 126 ms 197192 KB Output is correct
5 Correct 119 ms 196948 KB Output is correct
6 Correct 115 ms 196952 KB Output is correct
7 Correct 116 ms 197144 KB Output is correct
8 Correct 117 ms 197204 KB Output is correct
9 Correct 115 ms 197048 KB Output is correct
10 Correct 116 ms 197200 KB Output is correct
11 Correct 141 ms 197376 KB Output is correct
12 Correct 124 ms 197204 KB Output is correct
13 Correct 115 ms 197208 KB Output is correct
14 Correct 116 ms 197200 KB Output is correct
15 Correct 119 ms 197200 KB Output is correct
16 Correct 121 ms 197368 KB Output is correct
17 Correct 117 ms 197408 KB Output is correct
18 Correct 116 ms 197200 KB Output is correct
19 Correct 116 ms 197128 KB Output is correct
20 Correct 121 ms 197508 KB Output is correct
21 Correct 117 ms 197204 KB Output is correct
22 Correct 118 ms 197296 KB Output is correct
23 Correct 116 ms 197240 KB Output is correct
24 Correct 118 ms 197412 KB Output is correct
25 Correct 117 ms 197200 KB Output is correct
26 Correct 123 ms 197200 KB Output is correct
27 Correct 117 ms 197204 KB Output is correct
28 Incorrect 77 ms 197460 KB Output isn't correct
29 Halted 0 ms 0 KB -