Submission #969813

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
969813	2024-04-25T15:55:00 Z	pcc	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	22 / 100	142 ms	195708 KB

skyscraper

#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];
      |       ^

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	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

Subtask #2

12.0 / 12.0

#	Verdict	Execution time	Memory	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

Subtask #3

0 / 14.0

#	Verdict	Execution time	Memory	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	-

Subtask #4

0 / 21.0

#	Verdict	Execution time	Memory	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	-

Subtask #5

0 / 43.0

#	Verdict	Execution time	Memory	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	-