oj.uz

Submission #249688

# Submission time Handle Problem Language Result Execution time Memory
249688 2020-07-15T14:43:30 Z receed Jakarta Skyscrapers (APIO15_skyscraper) C++14
36 / 100
 219 ms 262148 KB 
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <string>
#include <set>
#include <map>
#include <random>
#include <bitset>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using ul = unsigned long long;
using ld = long double;

const int N = 30001, M = 10000000;
map<pair<int, int>, vector<int>> li;
vector<pair<int, int>> g[M];
int d[M], used[M];

void adde(int u, int v, int w) {
    g[u].push_back({v, w});
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m, cb, cp, s, t;
    cin >> n >> m;
    rep(i, m) {
        cin >> cb >> cp;
        if (i == 0)
            s = cb;
        else if (i == 1)
            t = cb;
        li[{cp, cb % cp}].push_back(cb);
    }
    int cs = n;
    for (auto &pp : li) {
        auto p = pp.first;
        int ck = (n - p.second + p.first - 1) / p.first;
        rep(i, ck - 1) {
            adde(cs + i, cs + i + 1, 1);
            adde(cs + i + 1, cs + i, 1);
        }
        rep(i, ck)
            adde(cs + i, p.second + i * p.first, 0);
        for (int i : pp.second)
            adde(i, cs + (i - p.second) / p.first, 0);
        cs += ck;
    }
    deque<int> q {s};
    rep(i, cs)
        d[i] = M;
    d[s] = 0;
    while (!q.empty()) {
        int v = q.front();
        q.pop_front();
        if (used[v])
            continue;
        used[v] = 1;
        for (auto &p : g[v]) {
            if (p.second) {
                if (d[p.first] > d[v] + 1) {
                    d[p.first] = d[v] + 1;
                    q.push_back(p.first);
                }
            }
            else if (d[p.first] > d[v]) {
                d[p.first] = d[v];
                q.push_front(p.first);
            }
        }
    }
    if (d[t] == M)
        cout << -1;
    else
        cout << d[t];
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:86:12: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if (d[t] == M)
         ~~~^
skyscraper.cpp:66:10: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
     d[s] = 0;
     ~~~~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 235128 KB Output is correct
2 Correct 126 ms 235128 KB Output is correct
3 Correct 124 ms 235128 KB Output is correct
4 Correct 126 ms 235128 KB Output is correct
5 Correct 130 ms 235384 KB Output is correct
6 Correct 121 ms 235128 KB Output is correct
7 Correct 122 ms 235128 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 235128 KB Output is correct
2 Correct 127 ms 235128 KB Output is correct
3 Correct 123 ms 235128 KB Output is correct
4 Correct 124 ms 235128 KB Output is correct
5 Correct 132 ms 235128 KB Output is correct
6 Correct 136 ms 235176 KB Output is correct
7 Correct 127 ms 235128 KB Output is correct
8 Correct 135 ms 235128 KB Output is correct
9 Correct 127 ms 235184 KB Output is correct
10 Correct 136 ms 235384 KB Output is correct
11 Correct 130 ms 235640 KB Output is correct
12 Correct 125 ms 235256 KB Output is correct
13 Correct 128 ms 235256 KB Output is correct
14 Correct 132 ms 235640 KB Output is correct
15 Correct 134 ms 235640 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 235128 KB Output is correct
2 Correct 126 ms 235128 KB Output is correct
3 Correct 132 ms 235128 KB Output is correct
4 Correct 127 ms 235128 KB Output is correct
5 Correct 124 ms 235128 KB Output is correct
6 Correct 124 ms 235128 KB Output is correct
7 Correct 129 ms 235128 KB Output is correct
8 Correct 124 ms 235128 KB Output is correct
9 Correct 125 ms 235128 KB Output is correct
10 Correct 128 ms 235384 KB Output is correct
11 Correct 125 ms 235512 KB Output is correct
12 Correct 126 ms 235256 KB Output is correct
13 Correct 128 ms 235256 KB Output is correct
14 Correct 129 ms 235640 KB Output is correct
15 Correct 128 ms 235640 KB Output is correct
16 Correct 127 ms 235512 KB Output is correct
17 Correct 130 ms 236152 KB Output is correct
18 Correct 127 ms 235640 KB Output is correct
19 Correct 129 ms 235512 KB Output is correct
20 Correct 127 ms 235384 KB Output is correct
21 Correct 125 ms 235384 KB Output is correct
22 Correct 125 ms 235512 KB Output is correct
23 Correct 129 ms 235640 KB Output is correct
24 Correct 129 ms 236152 KB Output is correct
25 Correct 127 ms 235768 KB Output is correct
26 Correct 130 ms 235640 KB Output is correct
27 Correct 126 ms 235640 KB Output is correct
28 Correct 130 ms 236664 KB Output is correct
29 Correct 137 ms 238584 KB Output is correct
30 Correct 128 ms 236152 KB Output is correct
31 Correct 133 ms 237048 KB Output is correct
32 Correct 131 ms 236536 KB Output is correct
33 Correct 155 ms 241912 KB Output is correct
34 Correct 152 ms 241912 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 235128 KB Output is correct
2 Correct 130 ms 235128 KB Output is correct
3 Correct 131 ms 235128 KB Output is correct
4 Correct 126 ms 235128 KB Output is correct
5 Correct 124 ms 235128 KB Output is correct
6 Correct 127 ms 235128 KB Output is correct
7 Correct 126 ms 235256 KB Output is correct
8 Correct 126 ms 235128 KB Output is correct
9 Correct 130 ms 235140 KB Output is correct
10 Correct 126 ms 235256 KB Output is correct
11 Correct 127 ms 235512 KB Output is correct
12 Correct 127 ms 235256 KB Output is correct
13 Correct 127 ms 235268 KB Output is correct
14 Correct 132 ms 235768 KB Output is correct
15 Correct 129 ms 235644 KB Output is correct
16 Correct 130 ms 235512 KB Output is correct
17 Correct 131 ms 236280 KB Output is correct
18 Correct 128 ms 235640 KB Output is correct
19 Correct 130 ms 235568 KB Output is correct
20 Correct 133 ms 235384 KB Output is correct
21 Correct 131 ms 235384 KB Output is correct
22 Correct 131 ms 235512 KB Output is correct
23 Correct 127 ms 235640 KB Output is correct
24 Correct 128 ms 236152 KB Output is correct
25 Correct 130 ms 235784 KB Output is correct
26 Correct 128 ms 235640 KB Output is correct
27 Correct 132 ms 235640 KB Output is correct
28 Correct 132 ms 236664 KB Output is correct
29 Correct 143 ms 238584 KB Output is correct
30 Correct 138 ms 236152 KB Output is correct
31 Correct 131 ms 237048 KB Output is correct
32 Correct 129 ms 236664 KB Output is correct
33 Correct 154 ms 241912 KB Output is correct
34 Correct 153 ms 241916 KB Output is correct
35 Correct 164 ms 243576 KB Output is correct
36 Correct 132 ms 236752 KB Output is correct
37 Correct 183 ms 246648 KB Output is correct
38 Correct 189 ms 247160 KB Output is correct
39 Correct 184 ms 247160 KB Output is correct
40 Correct 188 ms 247160 KB Output is correct
41 Correct 195 ms 247160 KB Output is correct
42 Correct 133 ms 236148 KB Output is correct
43 Correct 135 ms 236148 KB Output is correct
44 Correct 132 ms 236024 KB Output is correct
45 Runtime error 198 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
46 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 235128 KB Output is correct
2 Correct 125 ms 235128 KB Output is correct
3 Correct 126 ms 235160 KB Output is correct
4 Correct 126 ms 235128 KB Output is correct
5 Correct 125 ms 235128 KB Output is correct
6 Correct 127 ms 235128 KB Output is correct
7 Correct 129 ms 235128 KB Output is correct
8 Correct 128 ms 235128 KB Output is correct
9 Correct 125 ms 235128 KB Output is correct
10 Correct 127 ms 235256 KB Output is correct
11 Correct 128 ms 235640 KB Output is correct
12 Correct 126 ms 235256 KB Output is correct
13 Correct 125 ms 235256 KB Output is correct
14 Correct 131 ms 235768 KB Output is correct
15 Correct 128 ms 235640 KB Output is correct
16 Correct 128 ms 235452 KB Output is correct
17 Correct 128 ms 236152 KB Output is correct
18 Correct 133 ms 235640 KB Output is correct
19 Correct 139 ms 235512 KB Output is correct
20 Correct 127 ms 235348 KB Output is correct
21 Correct 128 ms 235388 KB Output is correct
22 Correct 128 ms 235512 KB Output is correct
23 Correct 129 ms 235640 KB Output is correct
24 Correct 129 ms 236024 KB Output is correct
25 Correct 128 ms 235896 KB Output is correct
26 Correct 128 ms 235640 KB Output is correct
27 Correct 128 ms 235716 KB Output is correct
28 Correct 130 ms 236716 KB Output is correct
29 Correct 140 ms 238584 KB Output is correct
30 Correct 129 ms 236152 KB Output is correct
31 Correct 134 ms 237048 KB Output is correct
32 Correct 134 ms 236468 KB Output is correct
33 Correct 153 ms 241912 KB Output is correct
34 Correct 154 ms 242040 KB Output is correct
35 Correct 164 ms 243576 KB Output is correct
36 Correct 133 ms 236664 KB Output is correct
37 Correct 186 ms 246520 KB Output is correct
38 Correct 191 ms 247288 KB Output is correct
39 Correct 187 ms 247160 KB Output is correct
40 Correct 186 ms 247160 KB Output is correct
41 Correct 191 ms 247416 KB Output is correct
42 Correct 132 ms 236148 KB Output is correct
43 Correct 134 ms 236148 KB Output is correct
44 Correct 130 ms 236032 KB Output is correct
45 Runtime error 219 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
46 Halted 0 ms 0 KB -