oj.uz

Submission #166848

# Submission time Handle Problem Language Result Execution time Memory
166848 2019-12-04T10:23:31 Z Hideo Jakarta Skyscrapers (APIO15_skyscraper) C++14
0 / 100
 18 ms 1148 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 INF = 1e9 + 7;
 
int a[N], b[N], d[N];
int m, n;
 
map < pi, int > mp;
 
vector < pi > g[N];
 
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], &b[i]);
        a[i]++;
        if (mp[{a[i], b[i]}])
            b[i] = 0;
        mp[{a[i], b[i]}] = 1;
    }
    for (int i = 1; i <= n; i++){
        if (!b[i])
            continue;
        int pos = a[i], pw = b[i], c = 0;
        while (pos + pw <= m){
            pos += pw; c++;
            g[a[i]].pb(mk(pos, c));
            if (mp[{pos, pw}])
                break;
        }
        pos = a[i], pw = b[i], c = 0;
        while (pos - pw > 0){
            pos -= pw; c++;
            g[a[i]].pb(mk(pos, c));
            if (mp[{pos, pw}])
                break;
        }
    }
    priority_queue < pi > pq;
    pq.push(mk(0, a[1]));
    memset(d, 0x3f3f3f3f, sizeof(d));
    d[a[1]] = 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));
            }
        }
    }
    printf("%d", d[a[2]]);
}
 
/*
    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], &b[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1148 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 3 ms 1144 KB Output is correct
4 Incorrect 3 ms 1144 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 3 ms 1144 KB Output is correct
4 Incorrect 3 ms 1108 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1148 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 3 ms 1144 KB Output is correct
4 Incorrect 3 ms 1144 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 18 ms 1144 KB Output is correct
3 Correct 3 ms 1144 KB Output is correct
4 Incorrect 5 ms 1144 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1116 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 3 ms 1144 KB Output is correct
4 Incorrect 3 ms 1116 KB Output isn't correct
5 Halted 0 ms 0 KB -