oj.uz

Submission #166850

# Submission time Handle Problem Language Result Execution time Memory
166850 2019-12-04T10:43:49 Z Hideo Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 773 ms 262148 KB 
// Need to git gud and reach 1900+
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
using namespace std;

#define all(s) s.begin(), s.end()
#define ok puts("ok")
#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define vi vector < int >
#define pi pair < int, int >
#define prev prev123
#define next next123
#define pow pow123
#define left left123
#define right right123

const int N = 30007;
const int M = 5e6 + 3e5 + 7;
const int INF = 1e9 + 7;

pi a[N];
int d[M];
int m, n, s, f;

vector < pi > g[M];

main(){ // If you don't know what to do, check the text box at the bottom
    cin >> m >> n;
    for (int i = 1; i <= n; i++){
        scanf("%d%d", &a[i].fr, &a[i].sc);
        a[i].fr++;
    }
    s = a[1].fr, f = a[2].fr;
    sort(a + 1, a + n + 1);
    int k = unique(a + 1, a + n + 1) - a;
    for (int i = 1; i < k; i++){
        if (a[i].sc <= 173)
            g[a[i].fr].pb(mk(m + (a[i].fr - 1) * 173 + a[i].sc, 0));
        else {
            int pos = a[i].fr, pw = a[i].sc, c = 0;
            while (pos + pw <= m){
                pos += pw; c++;
                g[a[i].fr].pb(mk(pos, c));
            }
            pos = a[i].fr, c = 0;
            while (pos - pw > 0){
                pos -= pw; c++;
                g[a[i].fr].pb(mk(pos, c));
            }
        }
    }
    for (int i = 1; i <= m; i++){
        for (int j = 1; j <= 173; j++){
            if (i + j <= m){
                g[m + (i - 1) * 173 + j].pb(mk(m + (i + j - 1) * 173 + j, 1));
                g[m + (i - 1) * 173 + j].pb(mk(i + j, 1));
            }
            if (i - j > 0){
                g[m + (i - 1) * 173 + j].pb(mk(m + (i - j - 1) * 173 + j, 1));
                g[m + (i - 1) * 173 + j].pb(mk(i - j, 1));
            }
        }
    }
    priority_queue < pi > pq;
    pq.push(mk(0, s));
    memset(d, 0x3f3f3f3f, sizeof(d));
    d[s] = 0;
    while (!pq.empty()){
        int w = -pq.top().fr, v = pq.top().sc;
        pq.pop();
        if (d[v] < w)
            continue;
        for (pi to : g[v]){
            if (d[to.fr] > d[v] + to.sc){
                d[to.fr] = d[v] + to.sc;
                pq.push(mk(-d[to.fr], to.fr));
            }
        }
    }
    if (d[f] != d[0])
        printf("%d", d[f]);
    else
        puts("-1");
}

/*
    Totally not inspired by BenQ's template
    Things you should do:
    1. Look for stupid typos in code e.g 1 instead of -1 etc
    2. Check if there is no infinite loops
    3. "Measure twice, cut once"
    4. Stay focused
*/

Compilation message

skyscraper.cpp:33:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){ // If you don't know what to do, check the text box at the bottom
      ^
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a[i].fr, &a[i].sc);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 145576 KB Output is correct
2 Correct 157 ms 145656 KB Output is correct
3 Correct 155 ms 145528 KB Output is correct
4 Correct 156 ms 145528 KB Output is correct
5 Correct 156 ms 145528 KB Output is correct
6 Correct 152 ms 145552 KB Output is correct
7 Correct 157 ms 145528 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 145528 KB Output is correct
2 Correct 155 ms 145524 KB Output is correct
3 Correct 204 ms 145636 KB Output is correct
4 Correct 157 ms 145600 KB Output is correct
5 Correct 156 ms 145656 KB Output is correct
6 Correct 151 ms 145524 KB Output is correct
7 Correct 157 ms 145700 KB Output is correct
8 Correct 195 ms 145532 KB Output is correct
9 Correct 153 ms 145580 KB Output is correct
10 Correct 153 ms 145784 KB Output is correct
11 Correct 160 ms 145916 KB Output is correct
12 Correct 158 ms 145800 KB Output is correct
13 Correct 159 ms 145808 KB Output is correct
14 Correct 159 ms 145912 KB Output is correct
15 Correct 153 ms 145912 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 145660 KB Output is correct
2 Correct 154 ms 145568 KB Output is correct
3 Correct 152 ms 145528 KB Output is correct
4 Correct 158 ms 145472 KB Output is correct
5 Correct 151 ms 145632 KB Output is correct
6 Correct 151 ms 145528 KB Output is correct
7 Correct 153 ms 145568 KB Output is correct
8 Correct 155 ms 145528 KB Output is correct
9 Correct 170 ms 145784 KB Output is correct
10 Correct 155 ms 145800 KB Output is correct
11 Correct 153 ms 146040 KB Output is correct
12 Correct 160 ms 145784 KB Output is correct
13 Correct 152 ms 145864 KB Output is correct
14 Correct 155 ms 146040 KB Output is correct
15 Correct 155 ms 145912 KB Output is correct
16 Correct 155 ms 146608 KB Output is correct
17 Correct 177 ms 151132 KB Output is correct
18 Correct 209 ms 159352 KB Output is correct
19 Correct 216 ms 161528 KB Output is correct
20 Correct 219 ms 161356 KB Output is correct
21 Correct 164 ms 148344 KB Output is correct
22 Correct 206 ms 159580 KB Output is correct
23 Correct 208 ms 158116 KB Output is correct
24 Correct 218 ms 160632 KB Output is correct
25 Correct 220 ms 161568 KB Output is correct
26 Correct 219 ms 161460 KB Output is correct
27 Correct 214 ms 161400 KB Output is correct
28 Correct 217 ms 161528 KB Output is correct
29 Correct 229 ms 161368 KB Output is correct
30 Correct 216 ms 161320 KB Output is correct
31 Correct 221 ms 161392 KB Output is correct
32 Correct 220 ms 161376 KB Output is correct
33 Correct 240 ms 161504 KB Output is correct
34 Correct 241 ms 161400 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 145544 KB Output is correct
2 Correct 154 ms 145528 KB Output is correct
3 Correct 184 ms 145524 KB Output is correct
4 Correct 151 ms 145532 KB Output is correct
5 Correct 152 ms 145656 KB Output is correct
6 Correct 150 ms 145528 KB Output is correct
7 Correct 151 ms 145528 KB Output is correct
8 Correct 154 ms 145528 KB Output is correct
9 Correct 151 ms 145660 KB Output is correct
10 Correct 153 ms 145944 KB Output is correct
11 Correct 153 ms 145956 KB Output is correct
12 Correct 153 ms 145784 KB Output is correct
13 Correct 152 ms 145912 KB Output is correct
14 Correct 152 ms 145884 KB Output is correct
15 Correct 154 ms 145904 KB Output is correct
16 Correct 156 ms 146608 KB Output is correct
17 Correct 181 ms 151212 KB Output is correct
18 Correct 205 ms 159264 KB Output is correct
19 Correct 211 ms 161352 KB Output is correct
20 Correct 215 ms 161540 KB Output is correct
21 Correct 164 ms 148344 KB Output is correct
22 Correct 206 ms 159608 KB Output is correct
23 Correct 205 ms 158276 KB Output is correct
24 Correct 217 ms 160536 KB Output is correct
25 Correct 218 ms 161544 KB Output is correct
26 Correct 219 ms 161272 KB Output is correct
27 Correct 218 ms 161400 KB Output is correct
28 Correct 223 ms 161564 KB Output is correct
29 Correct 230 ms 161504 KB Output is correct
30 Correct 218 ms 161272 KB Output is correct
31 Correct 220 ms 161280 KB Output is correct
32 Correct 222 ms 161508 KB Output is correct
33 Correct 245 ms 161568 KB Output is correct
34 Correct 245 ms 161400 KB Output is correct
35 Correct 229 ms 157524 KB Output is correct
36 Correct 195 ms 154076 KB Output is correct
37 Correct 263 ms 161884 KB Output is correct
38 Correct 262 ms 162500 KB Output is correct
39 Correct 260 ms 162488 KB Output is correct
40 Correct 259 ms 162552 KB Output is correct
41 Correct 266 ms 162672 KB Output is correct
42 Correct 224 ms 161784 KB Output is correct
43 Correct 226 ms 161784 KB Output is correct
44 Correct 222 ms 161820 KB Output is correct
45 Correct 307 ms 163820 KB Output is correct
46 Correct 308 ms 163736 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 145748 KB Output is correct
2 Correct 153 ms 145528 KB Output is correct
3 Correct 159 ms 145504 KB Output is correct
4 Correct 156 ms 145488 KB Output is correct
5 Correct 159 ms 145528 KB Output is correct
6 Correct 152 ms 145528 KB Output is correct
7 Correct 151 ms 145524 KB Output is correct
8 Correct 151 ms 145532 KB Output is correct
9 Correct 150 ms 145564 KB Output is correct
10 Correct 158 ms 145936 KB Output is correct
11 Correct 157 ms 145856 KB Output is correct
12 Correct 153 ms 145784 KB Output is correct
13 Correct 155 ms 145784 KB Output is correct
14 Correct 344 ms 145888 KB Output is correct
15 Correct 152 ms 145916 KB Output is correct
16 Correct 156 ms 146664 KB Output is correct
17 Correct 178 ms 151160 KB Output is correct
18 Correct 206 ms 159280 KB Output is correct
19 Correct 209 ms 161432 KB Output is correct
20 Correct 210 ms 161400 KB Output is correct
21 Correct 161 ms 148216 KB Output is correct
22 Correct 205 ms 159608 KB Output is correct
23 Correct 201 ms 158072 KB Output is correct
24 Correct 212 ms 160604 KB Output is correct
25 Correct 211 ms 161400 KB Output is correct
26 Correct 217 ms 161372 KB Output is correct
27 Correct 212 ms 161272 KB Output is correct
28 Correct 221 ms 161400 KB Output is correct
29 Correct 226 ms 161476 KB Output is correct
30 Correct 213 ms 161272 KB Output is correct
31 Correct 221 ms 161528 KB Output is correct
32 Correct 217 ms 161400 KB Output is correct
33 Correct 243 ms 161400 KB Output is correct
34 Correct 240 ms 161368 KB Output is correct
35 Correct 224 ms 157548 KB Output is correct
36 Correct 189 ms 154232 KB Output is correct
37 Correct 258 ms 161860 KB Output is correct
38 Correct 259 ms 162600 KB Output is correct
39 Correct 259 ms 162688 KB Output is correct
40 Correct 261 ms 162424 KB Output is correct
41 Correct 276 ms 162808 KB Output is correct
42 Correct 221 ms 161912 KB Output is correct
43 Correct 222 ms 161784 KB Output is correct
44 Correct 222 ms 161784 KB Output is correct
45 Correct 307 ms 163932 KB Output is correct
46 Correct 309 ms 163832 KB Output is correct
47 Correct 773 ms 249860 KB Output is correct
48 Runtime error 609 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
49 Halted 0 ms 0 KB -