oj.uz

Submission #969822

# Submission time Handle Problem Language Result Execution time Memory
969822 2024-04-25T16:08:23 Z pcc Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 1000 ms 262144 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+10;
const int mxn = 3e4+10;
const int mxe = mxn*sqrt(mxn)*3;
const int mxv = mxn*sqrt(mxn)*2;

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;
		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 91 ms 131308 KB Output is correct
2 Correct 77 ms 131612 KB Output is correct
3 Correct 75 ms 131460 KB Output is correct
4 Correct 77 ms 131412 KB Output is correct
5 Correct 73 ms 131412 KB Output is correct
6 Correct 73 ms 131500 KB Output is correct
7 Correct 72 ms 131408 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 131408 KB Output is correct
2 Correct 75 ms 131320 KB Output is correct
3 Correct 73 ms 131412 KB Output is correct
4 Correct 72 ms 131556 KB Output is correct
5 Correct 73 ms 131408 KB Output is correct
6 Correct 72 ms 131404 KB Output is correct
7 Correct 73 ms 131412 KB Output is correct
8 Correct 73 ms 131492 KB Output is correct
9 Correct 72 ms 131504 KB Output is correct
10 Correct 75 ms 131616 KB Output is correct
11 Correct 74 ms 131680 KB Output is correct
12 Correct 75 ms 131568 KB Output is correct
13 Correct 73 ms 131408 KB Output is correct
14 Correct 91 ms 131760 KB Output is correct
15 Correct 73 ms 131668 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 131540 KB Output is correct
2 Correct 73 ms 131556 KB Output is correct
3 Correct 73 ms 131412 KB Output is correct
4 Correct 77 ms 131492 KB Output is correct
5 Correct 73 ms 131408 KB Output is correct
6 Correct 75 ms 131408 KB Output is correct
7 Correct 73 ms 131380 KB Output is correct
8 Correct 74 ms 131404 KB Output is correct
9 Correct 83 ms 131508 KB Output is correct
10 Correct 74 ms 131408 KB Output is correct
11 Correct 75 ms 131668 KB Output is correct
12 Correct 73 ms 131408 KB Output is correct
13 Correct 74 ms 131408 KB Output is correct
14 Correct 74 ms 131664 KB Output is correct
15 Correct 74 ms 131664 KB Output is correct
16 Correct 88 ms 131668 KB Output is correct
17 Correct 78 ms 131668 KB Output is correct
18 Correct 83 ms 131916 KB Output is correct
19 Correct 79 ms 131408 KB Output is correct
20 Correct 75 ms 131592 KB Output is correct
21 Correct 76 ms 131700 KB Output is correct
22 Correct 74 ms 131672 KB Output is correct
23 Correct 74 ms 131448 KB Output is correct
24 Correct 78 ms 131768 KB Output is correct
25 Correct 75 ms 131668 KB Output is correct
26 Correct 74 ms 131512 KB Output is correct
27 Correct 80 ms 131432 KB Output is correct
28 Correct 75 ms 131828 KB Output is correct
29 Correct 76 ms 133712 KB Output is correct
30 Correct 73 ms 131420 KB Output is correct
31 Correct 85 ms 133712 KB Output is correct
32 Correct 83 ms 131704 KB Output is correct
33 Correct 79 ms 136276 KB Output is correct
34 Correct 79 ms 136276 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 131324 KB Output is correct
2 Correct 73 ms 131412 KB Output is correct
3 Correct 73 ms 131416 KB Output is correct
4 Correct 74 ms 131608 KB Output is correct
5 Correct 72 ms 131408 KB Output is correct
6 Correct 74 ms 131500 KB Output is correct
7 Correct 77 ms 131412 KB Output is correct
8 Correct 74 ms 131412 KB Output is correct
9 Correct 75 ms 131420 KB Output is correct
10 Correct 76 ms 131408 KB Output is correct
11 Correct 82 ms 131896 KB Output is correct
12 Correct 75 ms 131576 KB Output is correct
13 Correct 74 ms 131412 KB Output is correct
14 Correct 74 ms 131668 KB Output is correct
15 Correct 75 ms 131664 KB Output is correct
16 Correct 81 ms 131752 KB Output is correct
17 Correct 81 ms 131604 KB Output is correct
18 Correct 74 ms 131572 KB Output is correct
19 Correct 74 ms 131408 KB Output is correct
20 Correct 73 ms 131500 KB Output is correct
21 Correct 78 ms 131552 KB Output is correct
22 Correct 73 ms 131668 KB Output is correct
23 Correct 74 ms 131664 KB Output is correct
24 Correct 78 ms 131672 KB Output is correct
25 Correct 73 ms 131668 KB Output is correct
26 Correct 73 ms 131592 KB Output is correct
27 Correct 80 ms 131412 KB Output is correct
28 Correct 75 ms 131732 KB Output is correct
29 Correct 76 ms 133712 KB Output is correct
30 Correct 75 ms 131408 KB Output is correct
31 Correct 75 ms 133716 KB Output is correct
32 Correct 90 ms 131664 KB Output is correct
33 Correct 80 ms 136280 KB Output is correct
34 Correct 77 ms 136272 KB Output is correct
35 Correct 112 ms 138832 KB Output is correct
36 Correct 76 ms 131920 KB Output is correct
37 Correct 90 ms 138320 KB Output is correct
38 Correct 95 ms 139348 KB Output is correct
39 Correct 98 ms 139348 KB Output is correct
40 Correct 96 ms 139304 KB Output is correct
41 Correct 95 ms 139344 KB Output is correct
42 Correct 81 ms 131668 KB Output is correct
43 Correct 80 ms 131944 KB Output is correct
44 Correct 80 ms 131668 KB Output is correct
45 Correct 113 ms 148988 KB Output is correct
46 Correct 109 ms 149328 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 131364 KB Output is correct
2 Correct 74 ms 131412 KB Output is correct
3 Correct 73 ms 131556 KB Output is correct
4 Correct 72 ms 131412 KB Output is correct
5 Correct 85 ms 131408 KB Output is correct
6 Correct 77 ms 131408 KB Output is correct
7 Correct 73 ms 131408 KB Output is correct
8 Correct 73 ms 131408 KB Output is correct
9 Correct 73 ms 131320 KB Output is correct
10 Correct 79 ms 131668 KB Output is correct
11 Correct 74 ms 131664 KB Output is correct
12 Correct 74 ms 131576 KB Output is correct
13 Correct 73 ms 131408 KB Output is correct
14 Correct 85 ms 131604 KB Output is correct
15 Correct 77 ms 131668 KB Output is correct
16 Correct 74 ms 131668 KB Output is correct
17 Correct 74 ms 131628 KB Output is correct
18 Correct 73 ms 131668 KB Output is correct
19 Correct 73 ms 131408 KB Output is correct
20 Correct 74 ms 131664 KB Output is correct
21 Correct 74 ms 131668 KB Output is correct
22 Correct 73 ms 131668 KB Output is correct
23 Correct 76 ms 131664 KB Output is correct
24 Correct 74 ms 131596 KB Output is correct
25 Correct 74 ms 131664 KB Output is correct
26 Correct 74 ms 131580 KB Output is correct
27 Correct 74 ms 131544 KB Output is correct
28 Correct 74 ms 131836 KB Output is correct
29 Correct 84 ms 133712 KB Output is correct
30 Correct 82 ms 131452 KB Output is correct
31 Correct 77 ms 133812 KB Output is correct
32 Correct 74 ms 131660 KB Output is correct
33 Correct 83 ms 136320 KB Output is correct
34 Correct 80 ms 136276 KB Output is correct
35 Correct 92 ms 138836 KB Output is correct
36 Correct 75 ms 131932 KB Output is correct
37 Correct 108 ms 138332 KB Output is correct
38 Correct 109 ms 139348 KB Output is correct
39 Correct 97 ms 139348 KB Output is correct
40 Correct 96 ms 139284 KB Output is correct
41 Correct 98 ms 139512 KB Output is correct
42 Correct 79 ms 131672 KB Output is correct
43 Correct 75 ms 131696 KB Output is correct
44 Correct 80 ms 131924 KB Output is correct
45 Correct 113 ms 148884 KB Output is correct
46 Correct 109 ms 148984 KB Output is correct
47 Correct 127 ms 153428 KB Output is correct
48 Correct 97 ms 141140 KB Output is correct
49 Correct 93 ms 138520 KB Output is correct
50 Correct 83 ms 137808 KB Output is correct
51 Correct 107 ms 144244 KB Output is correct
52 Correct 114 ms 144528 KB Output is correct
53 Correct 93 ms 139352 KB Output is correct
54 Correct 73 ms 131664 KB Output is correct
55 Correct 81 ms 133712 KB Output is correct
56 Correct 85 ms 134180 KB Output is correct
57 Correct 97 ms 145744 KB Output is correct
58 Correct 80 ms 136016 KB Output is correct
59 Correct 81 ms 136056 KB Output is correct
60 Correct 81 ms 136436 KB Output is correct
61 Correct 84 ms 136676 KB Output is correct
62 Correct 105 ms 149100 KB Output is correct
63 Correct 217 ms 197200 KB Output is correct
64 Correct 241 ms 211456 KB Output is correct
65 Execution timed out 2404 ms 262144 KB Time limit exceeded
66 Halted 0 ms 0 KB -