oj.uz

Submission #969828

# Submission time Handle Problem Language Result Execution time Memory
969828 2024-04-25T16:13:01 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<short,short>
#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)*2.5;
const int mxv = mxn*sqrt(mxn)*2.005;

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 87 ms 131876 KB Output is correct
2 Correct 92 ms 131668 KB Output is correct
3 Correct 77 ms 131668 KB Output is correct
4 Correct 77 ms 131748 KB Output is correct
5 Correct 85 ms 131876 KB Output is correct
6 Correct 92 ms 131712 KB Output is correct
7 Correct 86 ms 131724 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 131880 KB Output is correct
2 Correct 90 ms 131808 KB Output is correct
3 Correct 85 ms 131876 KB Output is correct
4 Correct 79 ms 131876 KB Output is correct
5 Correct 83 ms 131664 KB Output is correct
6 Correct 90 ms 131884 KB Output is correct
7 Correct 78 ms 131668 KB Output is correct
8 Correct 102 ms 131664 KB Output is correct
9 Correct 95 ms 131820 KB Output is correct
10 Correct 84 ms 131720 KB Output is correct
11 Correct 81 ms 132000 KB Output is correct
12 Correct 84 ms 131668 KB Output is correct
13 Correct 92 ms 131872 KB Output is correct
14 Correct 78 ms 132016 KB Output is correct
15 Correct 82 ms 131992 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 131736 KB Output is correct
2 Correct 77 ms 131668 KB Output is correct
3 Correct 78 ms 131884 KB Output is correct
4 Correct 79 ms 131668 KB Output is correct
5 Correct 78 ms 131664 KB Output is correct
6 Correct 79 ms 131788 KB Output is correct
7 Correct 82 ms 131668 KB Output is correct
8 Correct 91 ms 131880 KB Output is correct
9 Correct 77 ms 131648 KB Output is correct
10 Correct 78 ms 131920 KB Output is correct
11 Correct 84 ms 131924 KB Output is correct
12 Correct 87 ms 131912 KB Output is correct
13 Correct 94 ms 131684 KB Output is correct
14 Correct 95 ms 131884 KB Output is correct
15 Correct 79 ms 131920 KB Output is correct
16 Correct 79 ms 132180 KB Output is correct
17 Correct 80 ms 133976 KB Output is correct
18 Correct 78 ms 132016 KB Output is correct
19 Correct 82 ms 131820 KB Output is correct
20 Correct 79 ms 131664 KB Output is correct
21 Correct 77 ms 131928 KB Output is correct
22 Correct 78 ms 131868 KB Output is correct
23 Correct 94 ms 131924 KB Output is correct
24 Correct 81 ms 131920 KB Output is correct
25 Correct 83 ms 132136 KB Output is correct
26 Correct 77 ms 131920 KB Output is correct
27 Correct 79 ms 131924 KB Output is correct
28 Correct 80 ms 134080 KB Output is correct
29 Correct 97 ms 136276 KB Output is correct
30 Correct 79 ms 133972 KB Output is correct
31 Correct 78 ms 133964 KB Output is correct
32 Correct 79 ms 133968 KB Output is correct
33 Correct 101 ms 136528 KB Output is correct
34 Correct 82 ms 136532 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 131708 KB Output is correct
2 Correct 77 ms 131880 KB Output is correct
3 Correct 76 ms 131828 KB Output is correct
4 Correct 77 ms 131724 KB Output is correct
5 Correct 76 ms 131668 KB Output is correct
6 Correct 77 ms 131728 KB Output is correct
7 Correct 77 ms 131728 KB Output is correct
8 Correct 83 ms 131768 KB Output is correct
9 Correct 87 ms 131668 KB Output is correct
10 Correct 85 ms 131760 KB Output is correct
11 Correct 88 ms 131924 KB Output is correct
12 Correct 83 ms 131668 KB Output is correct
13 Correct 87 ms 131888 KB Output is correct
14 Correct 85 ms 132176 KB Output is correct
15 Correct 80 ms 131920 KB Output is correct
16 Correct 80 ms 131848 KB Output is correct
17 Correct 80 ms 133976 KB Output is correct
18 Correct 90 ms 131928 KB Output is correct
19 Correct 77 ms 132104 KB Output is correct
20 Correct 77 ms 131668 KB Output is correct
21 Correct 79 ms 132020 KB Output is correct
22 Correct 82 ms 131924 KB Output is correct
23 Correct 86 ms 132016 KB Output is correct
24 Correct 81 ms 131932 KB Output is correct
25 Correct 79 ms 131920 KB Output is correct
26 Correct 96 ms 131924 KB Output is correct
27 Correct 82 ms 131760 KB Output is correct
28 Correct 80 ms 134228 KB Output is correct
29 Correct 81 ms 136272 KB Output is correct
30 Correct 78 ms 133768 KB Output is correct
31 Correct 80 ms 133972 KB Output is correct
32 Correct 79 ms 133928 KB Output is correct
33 Correct 84 ms 136528 KB Output is correct
34 Correct 83 ms 136524 KB Output is correct
35 Correct 97 ms 138932 KB Output is correct
36 Correct 81 ms 134484 KB Output is correct
37 Correct 95 ms 138680 KB Output is correct
38 Correct 112 ms 139856 KB Output is correct
39 Correct 100 ms 139856 KB Output is correct
40 Correct 112 ms 139604 KB Output is correct
41 Correct 100 ms 139856 KB Output is correct
42 Correct 88 ms 134108 KB Output is correct
43 Correct 101 ms 134124 KB Output is correct
44 Correct 85 ms 132176 KB Output is correct
45 Correct 137 ms 149356 KB Output is correct
46 Correct 130 ms 149332 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 131876 KB Output is correct
2 Correct 89 ms 131712 KB Output is correct
3 Correct 79 ms 131668 KB Output is correct
4 Correct 78 ms 131716 KB Output is correct
5 Correct 78 ms 131676 KB Output is correct
6 Correct 79 ms 131688 KB Output is correct
7 Correct 81 ms 131664 KB Output is correct
8 Correct 79 ms 131720 KB Output is correct
9 Correct 89 ms 131668 KB Output is correct
10 Correct 79 ms 131924 KB Output is correct
11 Correct 85 ms 131928 KB Output is correct
12 Correct 81 ms 131804 KB Output is correct
13 Correct 80 ms 131796 KB Output is correct
14 Correct 80 ms 131924 KB Output is correct
15 Correct 79 ms 131924 KB Output is correct
16 Correct 82 ms 131980 KB Output is correct
17 Correct 79 ms 134164 KB Output is correct
18 Correct 79 ms 131920 KB Output is correct
19 Correct 78 ms 131920 KB Output is correct
20 Correct 78 ms 131848 KB Output is correct
21 Correct 86 ms 132020 KB Output is correct
22 Correct 78 ms 131988 KB Output is correct
23 Correct 79 ms 132016 KB Output is correct
24 Correct 92 ms 131924 KB Output is correct
25 Correct 91 ms 132008 KB Output is correct
26 Correct 83 ms 131744 KB Output is correct
27 Correct 78 ms 131920 KB Output is correct
28 Correct 90 ms 134224 KB Output is correct
29 Correct 92 ms 136272 KB Output is correct
30 Correct 91 ms 133968 KB Output is correct
31 Correct 80 ms 133968 KB Output is correct
32 Correct 86 ms 133952 KB Output is correct
33 Correct 101 ms 136516 KB Output is correct
34 Correct 92 ms 136532 KB Output is correct
35 Correct 107 ms 138996 KB Output is correct
36 Correct 88 ms 134524 KB Output is correct
37 Correct 110 ms 138680 KB Output is correct
38 Correct 106 ms 139832 KB Output is correct
39 Correct 117 ms 139608 KB Output is correct
40 Correct 105 ms 139860 KB Output is correct
41 Correct 106 ms 139836 KB Output is correct
42 Correct 83 ms 134004 KB Output is correct
43 Correct 81 ms 133972 KB Output is correct
44 Correct 93 ms 131784 KB Output is correct
45 Correct 145 ms 149328 KB Output is correct
46 Correct 119 ms 149240 KB Output is correct
47 Correct 130 ms 155904 KB Output is correct
48 Correct 118 ms 143328 KB Output is correct
49 Correct 91 ms 138812 KB Output is correct
50 Correct 86 ms 138068 KB Output is correct
51 Correct 111 ms 144568 KB Output is correct
52 Correct 114 ms 144716 KB Output is correct
53 Correct 98 ms 139744 KB Output is correct
54 Correct 79 ms 133968 KB Output is correct
55 Correct 81 ms 136020 KB Output is correct
56 Correct 83 ms 134228 KB Output is correct
57 Correct 115 ms 146052 KB Output is correct
58 Correct 88 ms 136144 KB Output is correct
59 Correct 85 ms 136276 KB Output is correct
60 Correct 84 ms 136528 KB Output is correct
61 Correct 88 ms 136996 KB Output is correct
62 Correct 107 ms 149332 KB Output is correct
63 Correct 215 ms 197620 KB Output is correct
64 Correct 281 ms 212192 KB Output is correct
65 Execution timed out 2360 ms 262144 KB Time limit exceeded
66 Halted 0 ms 0 KB -