답안 #969813

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
969813 2024-04-25T15:55:00 Z pcc Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
142 ms 195708 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];
bool wei[mxe];
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<mxn> 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;
		if(now == T)break;
		done[now] = true;
		int d = dist[now];
		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;
}

Compilation message

skyscraper.cpp: In function 'void BFS()':
skyscraper.cpp:51:7: warning: unused variable 'd' [-Wunused-variable]
   51 |   int d = dist[now];
      |       ^
# 결과 실행 시간 메모리 Grader output
1 Correct 122 ms 195408 KB Output is correct
2 Correct 76 ms 195408 KB Output is correct
3 Correct 75 ms 195412 KB Output is correct
4 Correct 111 ms 195668 KB Output is correct
5 Correct 109 ms 195412 KB Output is correct
6 Correct 109 ms 195468 KB Output is correct
7 Correct 111 ms 195452 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 111 ms 195312 KB Output is correct
2 Correct 80 ms 195412 KB Output is correct
3 Correct 75 ms 195408 KB Output is correct
4 Correct 109 ms 195412 KB Output is correct
5 Correct 119 ms 195408 KB Output is correct
6 Correct 110 ms 195408 KB Output is correct
7 Correct 110 ms 195408 KB Output is correct
8 Correct 109 ms 195464 KB Output is correct
9 Correct 110 ms 195360 KB Output is correct
10 Correct 108 ms 195408 KB Output is correct
11 Correct 109 ms 195408 KB Output is correct
12 Correct 108 ms 195416 KB Output is correct
13 Correct 117 ms 195408 KB Output is correct
14 Correct 110 ms 195664 KB Output is correct
15 Correct 124 ms 195672 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 195352 KB Output is correct
2 Correct 78 ms 195436 KB Output is correct
3 Correct 77 ms 195376 KB Output is correct
4 Correct 108 ms 195252 KB Output is correct
5 Correct 110 ms 195280 KB Output is correct
6 Correct 108 ms 195356 KB Output is correct
7 Correct 110 ms 195264 KB Output is correct
8 Correct 111 ms 195320 KB Output is correct
9 Correct 110 ms 195412 KB Output is correct
10 Correct 109 ms 195464 KB Output is correct
11 Correct 109 ms 195648 KB Output is correct
12 Correct 110 ms 195320 KB Output is correct
13 Correct 112 ms 195380 KB Output is correct
14 Correct 109 ms 195576 KB Output is correct
15 Correct 109 ms 195668 KB Output is correct
16 Correct 111 ms 195416 KB Output is correct
17 Correct 110 ms 195604 KB Output is correct
18 Correct 109 ms 195408 KB Output is correct
19 Correct 112 ms 195452 KB Output is correct
20 Correct 109 ms 195412 KB Output is correct
21 Correct 109 ms 195592 KB Output is correct
22 Correct 110 ms 195568 KB Output is correct
23 Correct 108 ms 195408 KB Output is correct
24 Correct 130 ms 195668 KB Output is correct
25 Correct 134 ms 195624 KB Output is correct
26 Correct 120 ms 195324 KB Output is correct
27 Correct 109 ms 195408 KB Output is correct
28 Incorrect 78 ms 195664 KB Output isn't correct
29 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 195468 KB Output is correct
2 Correct 80 ms 195352 KB Output is correct
3 Correct 81 ms 195412 KB Output is correct
4 Correct 113 ms 195296 KB Output is correct
5 Correct 110 ms 195408 KB Output is correct
6 Correct 110 ms 195408 KB Output is correct
7 Correct 109 ms 195412 KB Output is correct
8 Correct 112 ms 195408 KB Output is correct
9 Correct 111 ms 195364 KB Output is correct
10 Correct 112 ms 195352 KB Output is correct
11 Correct 111 ms 195412 KB Output is correct
12 Correct 109 ms 195292 KB Output is correct
13 Correct 109 ms 195368 KB Output is correct
14 Correct 109 ms 195668 KB Output is correct
15 Correct 133 ms 195664 KB Output is correct
16 Correct 108 ms 195412 KB Output is correct
17 Correct 108 ms 195708 KB Output is correct
18 Correct 110 ms 195492 KB Output is correct
19 Correct 113 ms 195444 KB Output is correct
20 Correct 108 ms 195408 KB Output is correct
21 Correct 132 ms 195384 KB Output is correct
22 Correct 110 ms 195412 KB Output is correct
23 Correct 110 ms 195416 KB Output is correct
24 Correct 109 ms 195664 KB Output is correct
25 Correct 112 ms 195668 KB Output is correct
26 Correct 111 ms 195408 KB Output is correct
27 Correct 120 ms 195408 KB Output is correct
28 Incorrect 77 ms 195664 KB Output isn't correct
29 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 195368 KB Output is correct
2 Correct 85 ms 195416 KB Output is correct
3 Correct 77 ms 195412 KB Output is correct
4 Correct 108 ms 195464 KB Output is correct
5 Correct 112 ms 195468 KB Output is correct
6 Correct 109 ms 195252 KB Output is correct
7 Correct 111 ms 195456 KB Output is correct
8 Correct 107 ms 195408 KB Output is correct
9 Correct 124 ms 195412 KB Output is correct
10 Correct 110 ms 195444 KB Output is correct
11 Correct 110 ms 195444 KB Output is correct
12 Correct 111 ms 195412 KB Output is correct
13 Correct 142 ms 195284 KB Output is correct
14 Correct 125 ms 195668 KB Output is correct
15 Correct 110 ms 195668 KB Output is correct
16 Correct 113 ms 195448 KB Output is correct
17 Correct 117 ms 195668 KB Output is correct
18 Correct 128 ms 195504 KB Output is correct
19 Correct 116 ms 195560 KB Output is correct
20 Correct 118 ms 195532 KB Output is correct
21 Correct 115 ms 195516 KB Output is correct
22 Correct 111 ms 195580 KB Output is correct
23 Correct 125 ms 195404 KB Output is correct
24 Correct 127 ms 195668 KB Output is correct
25 Correct 109 ms 195620 KB Output is correct
26 Correct 129 ms 195384 KB Output is correct
27 Correct 114 ms 195404 KB Output is correct
28 Incorrect 76 ms 195668 KB Output isn't correct
29 Halted 0 ms 0 KB -