Submission #969819

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
969819	2024-04-25T16:00:32 Z	pcc	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	22 / 100	141 ms	197540 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];
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

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

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

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

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

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