#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
const int SQ = 1500;
const int MN = 30030;
struct chash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
size_t operator()(ii x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(splitmix64(x.first+FIXED_RANDOM)+x.second+FIXED_RANDOM);
}
};
unordered_map<ii,int, chash> dist;
ii ok[MN];
vi go[MN];
bitset<MN> vs;
int dx[2] = {-1,1};
short had[MN][SQ];
int ged(int u, int p) {
if(p < SQ) {return had[u][p];}
if(dist.count({u,p})) {
return dist[{u,p}];
}
return -1;
}
void sed(int u, int p, int val) {
if(p < SQ) {
had[u][p] = val;
return;}
dist[{u,p}] = val;
}
int main() {
ios::sync_with_stdio(0);cin.tie(0);
int n,m;
cin >> n >> m;
memset(had,-1,sizeof(had));
for(int i=0;i<m;i++) {
int a,p;
cin >> a >> p;
ok[i] = {a,p};
go[a].push_back(p);
}
deque<ii> q;
int sr = ok[0].first;
vs.set(sr);
for(int i=0;i<go[sr].size();i++) {
if(ged(sr,go[sr][i]) == -1) {
q.push_front({sr,go[sr][i]});
sed(sr,go[sr][i],0);
}
}
int res = -1;
int fin = ok[1].first;
while(!q.empty()) {
ii co = q.front();q.pop_front();
int u = co.first;
int p = co.second;
int di = ged(u,p);
//cout << "look " << u << " " << p << " = " << di << '\n';
if(u == fin) {
res = di;break;
}
if(!vs[u]) {
vs.set(u);
//cout << "unlock " << u << '\n';
for(int i=0;i<go[u].size();i++) {
if(ged(u,go[u][i]) == -1) {
q.push_front({u,go[u][i]});
sed(u,go[u][i],di);
}
}
q.push_front(co);
continue;
}
for(int i=0;i<2;i++) {
int v = u+dx[i]*p;
if(v < 0 || v >= n) {continue;}
if(ged(v,p) != -1) {continue;}
sed(v,p,di+1);
q.push_back({v,p});
}
}
cout << res << '\n';
}
Compilation message
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:60:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<go[sr].size();i++) {
~^~~~~~~~~~~~~~
skyscraper.cpp:80:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<go[u].size();i++) {
~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
89208 KB |
Output is correct |
2 |
Correct |
48 ms |
89216 KB |
Output is correct |
3 |
Correct |
48 ms |
89208 KB |
Output is correct |
4 |
Correct |
48 ms |
89208 KB |
Output is correct |
5 |
Correct |
49 ms |
89208 KB |
Output is correct |
6 |
Correct |
49 ms |
89208 KB |
Output is correct |
7 |
Correct |
67 ms |
89208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
89208 KB |
Output is correct |
2 |
Correct |
49 ms |
89208 KB |
Output is correct |
3 |
Correct |
49 ms |
89208 KB |
Output is correct |
4 |
Correct |
48 ms |
89212 KB |
Output is correct |
5 |
Correct |
50 ms |
89208 KB |
Output is correct |
6 |
Correct |
48 ms |
89208 KB |
Output is correct |
7 |
Correct |
48 ms |
89208 KB |
Output is correct |
8 |
Correct |
59 ms |
89208 KB |
Output is correct |
9 |
Correct |
48 ms |
89208 KB |
Output is correct |
10 |
Correct |
49 ms |
89208 KB |
Output is correct |
11 |
Correct |
49 ms |
89208 KB |
Output is correct |
12 |
Correct |
49 ms |
89216 KB |
Output is correct |
13 |
Correct |
49 ms |
89208 KB |
Output is correct |
14 |
Correct |
48 ms |
89208 KB |
Output is correct |
15 |
Correct |
49 ms |
89208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
89208 KB |
Output is correct |
2 |
Correct |
50 ms |
89208 KB |
Output is correct |
3 |
Correct |
48 ms |
89208 KB |
Output is correct |
4 |
Correct |
50 ms |
89208 KB |
Output is correct |
5 |
Correct |
48 ms |
89208 KB |
Output is correct |
6 |
Correct |
49 ms |
89208 KB |
Output is correct |
7 |
Correct |
49 ms |
89336 KB |
Output is correct |
8 |
Correct |
48 ms |
89208 KB |
Output is correct |
9 |
Correct |
48 ms |
89208 KB |
Output is correct |
10 |
Correct |
49 ms |
89208 KB |
Output is correct |
11 |
Correct |
48 ms |
89208 KB |
Output is correct |
12 |
Correct |
51 ms |
89208 KB |
Output is correct |
13 |
Correct |
50 ms |
89208 KB |
Output is correct |
14 |
Correct |
51 ms |
89208 KB |
Output is correct |
15 |
Correct |
48 ms |
89208 KB |
Output is correct |
16 |
Correct |
50 ms |
89208 KB |
Output is correct |
17 |
Correct |
51 ms |
89208 KB |
Output is correct |
18 |
Correct |
48 ms |
89208 KB |
Output is correct |
19 |
Correct |
50 ms |
89336 KB |
Output is correct |
20 |
Correct |
49 ms |
89336 KB |
Output is correct |
21 |
Correct |
49 ms |
89208 KB |
Output is correct |
22 |
Correct |
49 ms |
89208 KB |
Output is correct |
23 |
Correct |
50 ms |
89208 KB |
Output is correct |
24 |
Correct |
50 ms |
89336 KB |
Output is correct |
25 |
Correct |
49 ms |
89208 KB |
Output is correct |
26 |
Correct |
51 ms |
89336 KB |
Output is correct |
27 |
Correct |
49 ms |
89208 KB |
Output is correct |
28 |
Correct |
52 ms |
89336 KB |
Output is correct |
29 |
Correct |
50 ms |
89188 KB |
Output is correct |
30 |
Correct |
50 ms |
89208 KB |
Output is correct |
31 |
Correct |
49 ms |
89212 KB |
Output is correct |
32 |
Correct |
49 ms |
89208 KB |
Output is correct |
33 |
Correct |
52 ms |
89208 KB |
Output is correct |
34 |
Correct |
51 ms |
89336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
49 ms |
89208 KB |
Output is correct |
2 |
Correct |
48 ms |
89208 KB |
Output is correct |
3 |
Correct |
49 ms |
89208 KB |
Output is correct |
4 |
Correct |
50 ms |
89208 KB |
Output is correct |
5 |
Correct |
49 ms |
89208 KB |
Output is correct |
6 |
Correct |
49 ms |
89208 KB |
Output is correct |
7 |
Correct |
48 ms |
89208 KB |
Output is correct |
8 |
Correct |
49 ms |
89208 KB |
Output is correct |
9 |
Correct |
49 ms |
89208 KB |
Output is correct |
10 |
Correct |
49 ms |
89212 KB |
Output is correct |
11 |
Correct |
49 ms |
89336 KB |
Output is correct |
12 |
Correct |
49 ms |
89208 KB |
Output is correct |
13 |
Correct |
48 ms |
89208 KB |
Output is correct |
14 |
Correct |
49 ms |
89336 KB |
Output is correct |
15 |
Correct |
51 ms |
89208 KB |
Output is correct |
16 |
Correct |
49 ms |
89208 KB |
Output is correct |
17 |
Correct |
50 ms |
89336 KB |
Output is correct |
18 |
Correct |
49 ms |
89208 KB |
Output is correct |
19 |
Correct |
48 ms |
89208 KB |
Output is correct |
20 |
Correct |
51 ms |
89336 KB |
Output is correct |
21 |
Correct |
49 ms |
89208 KB |
Output is correct |
22 |
Correct |
50 ms |
89208 KB |
Output is correct |
23 |
Correct |
51 ms |
89208 KB |
Output is correct |
24 |
Correct |
51 ms |
89336 KB |
Output is correct |
25 |
Correct |
49 ms |
89208 KB |
Output is correct |
26 |
Correct |
52 ms |
89228 KB |
Output is correct |
27 |
Correct |
49 ms |
89208 KB |
Output is correct |
28 |
Correct |
50 ms |
89336 KB |
Output is correct |
29 |
Correct |
50 ms |
89216 KB |
Output is correct |
30 |
Correct |
48 ms |
89208 KB |
Output is correct |
31 |
Correct |
49 ms |
89208 KB |
Output is correct |
32 |
Correct |
51 ms |
89208 KB |
Output is correct |
33 |
Correct |
53 ms |
89208 KB |
Output is correct |
34 |
Correct |
51 ms |
89336 KB |
Output is correct |
35 |
Correct |
57 ms |
90232 KB |
Output is correct |
36 |
Correct |
49 ms |
89336 KB |
Output is correct |
37 |
Correct |
54 ms |
89848 KB |
Output is correct |
38 |
Correct |
59 ms |
90232 KB |
Output is correct |
39 |
Correct |
55 ms |
89976 KB |
Output is correct |
40 |
Correct |
56 ms |
89976 KB |
Output is correct |
41 |
Correct |
58 ms |
90616 KB |
Output is correct |
42 |
Correct |
55 ms |
89848 KB |
Output is correct |
43 |
Correct |
54 ms |
89976 KB |
Output is correct |
44 |
Correct |
56 ms |
89848 KB |
Output is correct |
45 |
Correct |
65 ms |
90104 KB |
Output is correct |
46 |
Correct |
60 ms |
90104 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
49 ms |
89212 KB |
Output is correct |
2 |
Correct |
50 ms |
89208 KB |
Output is correct |
3 |
Correct |
48 ms |
89208 KB |
Output is correct |
4 |
Correct |
49 ms |
89264 KB |
Output is correct |
5 |
Correct |
48 ms |
89208 KB |
Output is correct |
6 |
Correct |
49 ms |
89208 KB |
Output is correct |
7 |
Correct |
48 ms |
89208 KB |
Output is correct |
8 |
Correct |
48 ms |
89208 KB |
Output is correct |
9 |
Correct |
48 ms |
89208 KB |
Output is correct |
10 |
Correct |
48 ms |
89208 KB |
Output is correct |
11 |
Correct |
49 ms |
89208 KB |
Output is correct |
12 |
Correct |
50 ms |
89208 KB |
Output is correct |
13 |
Correct |
49 ms |
89240 KB |
Output is correct |
14 |
Correct |
49 ms |
89208 KB |
Output is correct |
15 |
Correct |
48 ms |
89208 KB |
Output is correct |
16 |
Correct |
48 ms |
89208 KB |
Output is correct |
17 |
Correct |
48 ms |
89208 KB |
Output is correct |
18 |
Correct |
50 ms |
89208 KB |
Output is correct |
19 |
Correct |
50 ms |
89208 KB |
Output is correct |
20 |
Correct |
48 ms |
89336 KB |
Output is correct |
21 |
Correct |
49 ms |
89208 KB |
Output is correct |
22 |
Correct |
49 ms |
89208 KB |
Output is correct |
23 |
Correct |
49 ms |
89208 KB |
Output is correct |
24 |
Correct |
51 ms |
89336 KB |
Output is correct |
25 |
Correct |
51 ms |
89336 KB |
Output is correct |
26 |
Correct |
49 ms |
89208 KB |
Output is correct |
27 |
Correct |
50 ms |
89336 KB |
Output is correct |
28 |
Correct |
50 ms |
89336 KB |
Output is correct |
29 |
Correct |
51 ms |
89208 KB |
Output is correct |
30 |
Correct |
50 ms |
89208 KB |
Output is correct |
31 |
Correct |
51 ms |
89212 KB |
Output is correct |
32 |
Correct |
50 ms |
89208 KB |
Output is correct |
33 |
Correct |
51 ms |
89208 KB |
Output is correct |
34 |
Correct |
50 ms |
89208 KB |
Output is correct |
35 |
Correct |
57 ms |
90232 KB |
Output is correct |
36 |
Correct |
50 ms |
89336 KB |
Output is correct |
37 |
Correct |
54 ms |
89848 KB |
Output is correct |
38 |
Correct |
60 ms |
90196 KB |
Output is correct |
39 |
Correct |
54 ms |
89976 KB |
Output is correct |
40 |
Correct |
55 ms |
89976 KB |
Output is correct |
41 |
Correct |
62 ms |
90488 KB |
Output is correct |
42 |
Correct |
61 ms |
89848 KB |
Output is correct |
43 |
Correct |
52 ms |
89848 KB |
Output is correct |
44 |
Correct |
53 ms |
89976 KB |
Output is correct |
45 |
Correct |
66 ms |
90232 KB |
Output is correct |
46 |
Correct |
62 ms |
90104 KB |
Output is correct |
47 |
Correct |
59 ms |
90744 KB |
Output is correct |
48 |
Correct |
55 ms |
90104 KB |
Output is correct |
49 |
Correct |
55 ms |
89976 KB |
Output is correct |
50 |
Correct |
54 ms |
89848 KB |
Output is correct |
51 |
Correct |
76 ms |
92840 KB |
Output is correct |
52 |
Correct |
87 ms |
93352 KB |
Output is correct |
53 |
Correct |
59 ms |
90616 KB |
Output is correct |
54 |
Correct |
50 ms |
89208 KB |
Output is correct |
55 |
Correct |
50 ms |
89208 KB |
Output is correct |
56 |
Correct |
58 ms |
90616 KB |
Output is correct |
57 |
Correct |
49 ms |
89336 KB |
Output is correct |
58 |
Incorrect |
56 ms |
89720 KB |
Output isn't correct |
59 |
Halted |
0 ms |
0 KB |
- |