oj.uz

Submission #166849

# Submission time Handle Problem Language Result Execution time Memory
166849 2019-12-04T10:38:26 Z Hideo Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 526 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 = 6e6 + 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 <= 175)
            g[a[i].fr].pb(mk(m + (a[i].fr - 1) * 175 + 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 <= 175; j++){
            if (i + j <= m){
                g[m + (i - 1) * 175 + j].pb(mk(m + (i + j - 1) * 175 + j, 1));
                g[m + (i - 1) * 175 + j].pb(mk(i + j, 1));
            }
            if (i - j > 0){
                g[m + (i - 1) * 175 + j].pb(mk(m + (i - j - 1) * 175 + j, 1));
                g[m + (i - 1) * 175 + 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 171 ms 164728 KB Output is correct
2 Correct 170 ms 164856 KB Output is correct
3 Correct 170 ms 164856 KB Output is correct
4 Correct 177 ms 164936 KB Output is correct
5 Correct 177 ms 164832 KB Output is correct
6 Correct 168 ms 164708 KB Output is correct
7 Correct 179 ms 164876 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 164624 KB Output is correct
2 Correct 172 ms 164856 KB Output is correct
3 Correct 170 ms 164772 KB Output is correct
4 Correct 173 ms 164852 KB Output is correct
5 Correct 170 ms 164760 KB Output is correct
6 Correct 177 ms 164696 KB Output is correct
7 Correct 169 ms 164676 KB Output is correct
8 Correct 170 ms 164700 KB Output is correct
9 Correct 178 ms 164856 KB Output is correct
10 Correct 174 ms 165004 KB Output is correct
11 Correct 177 ms 164992 KB Output is correct
12 Correct 176 ms 165112 KB Output is correct
13 Correct 177 ms 164984 KB Output is correct
14 Correct 174 ms 164984 KB Output is correct
15 Correct 177 ms 165008 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 164668 KB Output is correct
2 Correct 175 ms 164732 KB Output is correct
3 Correct 176 ms 164764 KB Output is correct
4 Correct 175 ms 164712 KB Output is correct
5 Correct 176 ms 164816 KB Output is correct
6 Correct 175 ms 164700 KB Output is correct
7 Correct 176 ms 164728 KB Output is correct
8 Correct 170 ms 164720 KB Output is correct
9 Correct 171 ms 164840 KB Output is correct
10 Correct 175 ms 164916 KB Output is correct
11 Correct 175 ms 164984 KB Output is correct
12 Correct 176 ms 165020 KB Output is correct
13 Correct 176 ms 165016 KB Output is correct
14 Correct 172 ms 165084 KB Output is correct
15 Correct 177 ms 164984 KB Output is correct
16 Correct 181 ms 165880 KB Output is correct
17 Correct 201 ms 170644 KB Output is correct
18 Correct 227 ms 178680 KB Output is correct
19 Correct 234 ms 180688 KB Output is correct
20 Correct 238 ms 180856 KB Output is correct
21 Correct 182 ms 167544 KB Output is correct
22 Correct 232 ms 178936 KB Output is correct
23 Correct 228 ms 177528 KB Output is correct
24 Correct 234 ms 179960 KB Output is correct
25 Correct 241 ms 180728 KB Output is correct
26 Correct 235 ms 180728 KB Output is correct
27 Correct 252 ms 180688 KB Output is correct
28 Correct 239 ms 180796 KB Output is correct
29 Correct 305 ms 180764 KB Output is correct
30 Correct 234 ms 180648 KB Output is correct
31 Correct 243 ms 180796 KB Output is correct
32 Correct 238 ms 180692 KB Output is correct
33 Correct 266 ms 180856 KB Output is correct
34 Correct 266 ms 180768 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 164732 KB Output is correct
2 Correct 175 ms 164712 KB Output is correct
3 Correct 171 ms 164728 KB Output is correct
4 Correct 171 ms 164728 KB Output is correct
5 Correct 175 ms 164728 KB Output is correct
6 Correct 176 ms 164684 KB Output is correct
7 Correct 176 ms 164740 KB Output is correct
8 Correct 177 ms 164828 KB Output is correct
9 Correct 177 ms 164856 KB Output is correct
10 Correct 178 ms 164984 KB Output is correct
11 Correct 171 ms 164984 KB Output is correct
12 Correct 173 ms 165032 KB Output is correct
13 Correct 177 ms 164984 KB Output is correct
14 Correct 175 ms 165012 KB Output is correct
15 Correct 178 ms 165084 KB Output is correct
16 Correct 178 ms 165968 KB Output is correct
17 Correct 197 ms 170360 KB Output is correct
18 Correct 225 ms 178680 KB Output is correct
19 Correct 235 ms 180876 KB Output is correct
20 Correct 232 ms 180896 KB Output is correct
21 Correct 181 ms 167408 KB Output is correct
22 Correct 225 ms 178912 KB Output is correct
23 Correct 221 ms 177400 KB Output is correct
24 Correct 234 ms 179952 KB Output is correct
25 Correct 234 ms 180792 KB Output is correct
26 Correct 233 ms 180828 KB Output is correct
27 Correct 242 ms 180740 KB Output is correct
28 Correct 235 ms 180844 KB Output is correct
29 Correct 247 ms 180728 KB Output is correct
30 Correct 266 ms 180608 KB Output is correct
31 Correct 238 ms 180728 KB Output is correct
32 Correct 238 ms 180812 KB Output is correct
33 Correct 259 ms 180820 KB Output is correct
34 Correct 295 ms 180768 KB Output is correct
35 Correct 243 ms 176956 KB Output is correct
36 Correct 206 ms 173432 KB Output is correct
37 Correct 276 ms 181240 KB Output is correct
38 Correct 274 ms 181880 KB Output is correct
39 Correct 278 ms 181972 KB Output is correct
40 Correct 283 ms 181880 KB Output is correct
41 Correct 287 ms 181920 KB Output is correct
42 Correct 245 ms 181136 KB Output is correct
43 Correct 244 ms 181084 KB Output is correct
44 Correct 243 ms 181240 KB Output is correct
45 Correct 343 ms 183164 KB Output is correct
46 Correct 333 ms 183136 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 164688 KB Output is correct
2 Correct 175 ms 164988 KB Output is correct
3 Correct 175 ms 164728 KB Output is correct
4 Correct 176 ms 164712 KB Output is correct
5 Correct 175 ms 164728 KB Output is correct
6 Correct 178 ms 164840 KB Output is correct
7 Correct 175 ms 164728 KB Output is correct
8 Correct 174 ms 164732 KB Output is correct
9 Correct 176 ms 164856 KB Output is correct
10 Correct 178 ms 164956 KB Output is correct
11 Correct 180 ms 165084 KB Output is correct
12 Correct 180 ms 164972 KB Output is correct
13 Correct 178 ms 164984 KB Output is correct
14 Correct 172 ms 165008 KB Output is correct
15 Correct 178 ms 165060 KB Output is correct
16 Correct 178 ms 165880 KB Output is correct
17 Correct 205 ms 170588 KB Output is correct
18 Correct 228 ms 178680 KB Output is correct
19 Correct 235 ms 180704 KB Output is correct
20 Correct 233 ms 180728 KB Output is correct
21 Correct 187 ms 167416 KB Output is correct
22 Correct 222 ms 178936 KB Output is correct
23 Correct 226 ms 177476 KB Output is correct
24 Correct 238 ms 180112 KB Output is correct
25 Correct 237 ms 180728 KB Output is correct
26 Correct 239 ms 180732 KB Output is correct
27 Correct 245 ms 180856 KB Output is correct
28 Correct 244 ms 180728 KB Output is correct
29 Correct 247 ms 180772 KB Output is correct
30 Correct 243 ms 180856 KB Output is correct
31 Correct 246 ms 180728 KB Output is correct
32 Correct 244 ms 180700 KB Output is correct
33 Correct 270 ms 180728 KB Output is correct
34 Correct 265 ms 180796 KB Output is correct
35 Correct 243 ms 176888 KB Output is correct
36 Correct 214 ms 173304 KB Output is correct
37 Correct 297 ms 181208 KB Output is correct
38 Correct 280 ms 181880 KB Output is correct
39 Correct 281 ms 182008 KB Output is correct
40 Correct 282 ms 182028 KB Output is correct
41 Correct 281 ms 181880 KB Output is correct
42 Correct 245 ms 181208 KB Output is correct
43 Correct 245 ms 181116 KB Output is correct
44 Correct 244 ms 181240 KB Output is correct
45 Correct 330 ms 183160 KB Output is correct
46 Correct 333 ms 183160 KB Output is correct
47 Runtime error 526 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
48 Halted 0 ms 0 KB -