oj.uz

답안 #683469

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
683469 2023-01-18T13:19:30 Z nguyentunglam Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 223 ms 262144 KB 
#include<bits/stdc++.h>
#define forin(i, a, b) for(int i = a; i <= b; i++)
#define forde(i, a, b) for(int i = a; i >= b; i--)
#define forv(a, b) for(auto & a : b)
#define fi first
#define se second
#define ii pair<int, int>
#define endl "\n"
using namespace std;
const int N = 1e5 + 10, M = 1e7 + 10;
int b[N], p[N], cnt, f[M], d[N];
bool check[N], c[N];
pair<int, int> a[M];
vector<int> v[N], adj[M], g[N], tmp;
int main() {
    #define task ""
    cin.tie(0) -> sync_with_stdio(0);
    if (fopen ("task.inp", "r")) {
        freopen ("task.inp", "r", stdin);
        freopen ("task.out", "w", stdout);
    }
    if (fopen (task".inp", "r")) {
        freopen (task".inp", "r", stdin);
        freopen (task".out", "w", stdout);
    }
    int n, m; cin >> n >> m;
    int start = clock();
    for(int i = 0; i < m; i++) {
        cin >> b[i] >> p[i];
        p[i] = min(p[i], n);
        g[p[i]].push_back(b[i]);
    }
    for(int val = 1;  val <= n; val++) {
        for(int j : g[val]) {
            if (!c[j % val]) tmp.push_back(j % val), c[j % val] = 1;
        }
        for(int j : tmp) {
            for(int k = j; k < n; k += val) {
                d[k] = ++cnt;
                if (cnt > M - 1) return 0;
                a[cnt] = {k, val};
                if (k >= val) {
                    adj[cnt].push_back(d[k - val]);
                    adj[d[k - val]].push_back(cnt);
                }
            }
        }
        tmp.clear();
        for(int j : g[val]) v[j].push_back(d[j]), c[j % val] = 0;
        g[val].clear();
    }
    int ans;
    for(int i = 1; i <= cnt; i++) if (a[i].fi == b[1] && a[i].se == p[1]) ans = i;
    queue<int> q;
    for(int j : v[b[0]]) if (!f[j]) f[j] = 1, q.push(j);
    check[b[0]] = 1;
    while (!q.empty()) {
        int id = q.front();
        q.pop();
        if (id == ans) return cout << f[ans] - 1, 0;
        int u = a[id].fi, w = a[id].se;
        if (u - w >= 0 && !check[u - w]) {
            check[u - w] = 1;
            for(int j : v[u - w]) if (!f[j]) f[j] = f[id] + 1, q.push(j);
        }
        if (u + w < n && !check[u + w]) {
            check[u + w] = 1;
            for(int j : v[u + w]) if (!f[j]) f[j] = f[id] + 1, q.push(j);
        }
        forv(v, adj[id]) if (!f[v]) f[v] = f[id] + 1, q.push(v);
    }
    cout << -1;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:27:9: warning: unused variable 'start' [-Wunused-variable]
   27 |     int start = clock();
      |         ^~~~~
skyscraper.cpp:19:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen ("task.inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:20:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen ("task.out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:23:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen (task".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:24:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         freopen (task".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:60:44: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   60 |         if (id == ans) return cout << f[ans] - 1, 0;
      |                                       ~~~~~^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 239872 KB Output is correct
2 Correct 116 ms 239880 KB Output is correct
3 Correct 120 ms 239824 KB Output is correct
4 Correct 117 ms 239832 KB Output is correct
5 Correct 107 ms 239880 KB Output is correct
6 Correct 108 ms 239880 KB Output is correct
7 Correct 112 ms 239848 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 239808 KB Output is correct
2 Correct 115 ms 239880 KB Output is correct
3 Correct 106 ms 239828 KB Output is correct
4 Correct 113 ms 239872 KB Output is correct
5 Correct 118 ms 239948 KB Output is correct
6 Correct 110 ms 239860 KB Output is correct
7 Correct 115 ms 239784 KB Output is correct
8 Correct 114 ms 239884 KB Output is correct
9 Correct 108 ms 239780 KB Output is correct
10 Correct 112 ms 239952 KB Output is correct
11 Correct 108 ms 240072 KB Output is correct
12 Correct 112 ms 239924 KB Output is correct
13 Correct 110 ms 239812 KB Output is correct
14 Correct 113 ms 240232 KB Output is correct
15 Correct 108 ms 240076 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 239824 KB Output is correct
2 Correct 114 ms 239864 KB Output is correct
3 Correct 107 ms 239836 KB Output is correct
4 Correct 105 ms 239804 KB Output is correct
5 Correct 109 ms 239836 KB Output is correct
6 Correct 113 ms 239832 KB Output is correct
7 Correct 107 ms 239880 KB Output is correct
8 Correct 115 ms 239880 KB Output is correct
9 Correct 108 ms 239784 KB Output is correct
10 Correct 111 ms 239860 KB Output is correct
11 Correct 114 ms 240112 KB Output is correct
12 Correct 107 ms 239856 KB Output is correct
13 Correct 109 ms 240004 KB Output is correct
14 Correct 126 ms 240176 KB Output is correct
15 Correct 121 ms 240104 KB Output is correct
16 Correct 114 ms 240032 KB Output is correct
17 Correct 110 ms 240520 KB Output is correct
18 Correct 121 ms 240188 KB Output is correct
19 Correct 113 ms 240040 KB Output is correct
20 Correct 110 ms 239984 KB Output is correct
21 Correct 110 ms 239980 KB Output is correct
22 Correct 116 ms 240040 KB Output is correct
23 Correct 109 ms 240132 KB Output is correct
24 Correct 111 ms 240436 KB Output is correct
25 Correct 127 ms 240204 KB Output is correct
26 Correct 113 ms 240248 KB Output is correct
27 Correct 107 ms 240116 KB Output is correct
28 Correct 112 ms 240892 KB Output is correct
29 Correct 117 ms 242548 KB Output is correct
30 Correct 115 ms 240588 KB Output is correct
31 Correct 112 ms 241288 KB Output is correct
32 Correct 108 ms 240848 KB Output is correct
33 Correct 124 ms 245064 KB Output is correct
34 Correct 130 ms 245120 KB Output is correct

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 239832 KB Output is correct
2 Correct 113 ms 239844 KB Output is correct
3 Correct 109 ms 239840 KB Output is correct
4 Correct 119 ms 239796 KB Output is correct
5 Correct 106 ms 239800 KB Output is correct
6 Correct 111 ms 239880 KB Output is correct
7 Correct 112 ms 239780 KB Output is correct
8 Correct 117 ms 239824 KB Output is correct
9 Correct 113 ms 239844 KB Output is correct
10 Correct 123 ms 239944 KB Output is correct
11 Correct 123 ms 240076 KB Output is correct
12 Correct 106 ms 239884 KB Output is correct
13 Correct 109 ms 239940 KB Output is correct
14 Correct 109 ms 240088 KB Output is correct
15 Correct 111 ms 240216 KB Output is correct
16 Correct 116 ms 239996 KB Output is correct
17 Correct 108 ms 240588 KB Output is correct
18 Correct 107 ms 240116 KB Output is correct
19 Correct 108 ms 239996 KB Output is correct
20 Correct 107 ms 240076 KB Output is correct
21 Correct 107 ms 239940 KB Output is correct
22 Correct 107 ms 240100 KB Output is correct
23 Correct 108 ms 240216 KB Output is correct
24 Correct 113 ms 240520 KB Output is correct
25 Correct 108 ms 240252 KB Output is correct
26 Correct 107 ms 240188 KB Output is correct
27 Correct 112 ms 240224 KB Output is correct
28 Correct 109 ms 240956 KB Output is correct
29 Correct 120 ms 242556 KB Output is correct
30 Correct 129 ms 240532 KB Output is correct
31 Correct 109 ms 241332 KB Output is correct
32 Correct 109 ms 240860 KB Output is correct
33 Correct 131 ms 245168 KB Output is correct
34 Correct 129 ms 245112 KB Output is correct
35 Correct 133 ms 244676 KB Output is correct
36 Correct 110 ms 240648 KB Output is correct
37 Correct 137 ms 247944 KB Output is correct
38 Correct 139 ms 247696 KB Output is correct
39 Correct 127 ms 247352 KB Output is correct
40 Correct 141 ms 247544 KB Output is correct
41 Correct 127 ms 247500 KB Output is correct
42 Correct 124 ms 240796 KB Output is correct
43 Correct 115 ms 240848 KB Output is correct
44 Correct 113 ms 240716 KB Output is correct
45 Correct 220 ms 261480 KB Output is correct
46 Correct 199 ms 261492 KB Output is correct

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 239796 KB Output is correct
2 Correct 108 ms 239804 KB Output is correct
3 Correct 114 ms 239948 KB Output is correct
4 Correct 110 ms 239880 KB Output is correct
5 Correct 109 ms 239816 KB Output is correct
6 Correct 109 ms 239840 KB Output is correct
7 Correct 106 ms 239880 KB Output is correct
8 Correct 113 ms 239820 KB Output is correct
9 Correct 107 ms 239828 KB Output is correct
10 Correct 105 ms 239876 KB Output is correct
11 Correct 113 ms 240100 KB Output is correct
12 Correct 110 ms 239808 KB Output is correct
13 Correct 113 ms 239832 KB Output is correct
14 Correct 109 ms 240084 KB Output is correct
15 Correct 108 ms 240076 KB Output is correct
16 Correct 109 ms 240016 KB Output is correct
17 Correct 111 ms 240692 KB Output is correct
18 Correct 108 ms 240176 KB Output is correct
19 Correct 108 ms 240096 KB Output is correct
20 Correct 115 ms 239972 KB Output is correct
21 Correct 107 ms 239912 KB Output is correct
22 Correct 111 ms 240132 KB Output is correct
23 Correct 118 ms 240200 KB Output is correct
24 Correct 111 ms 240484 KB Output is correct
25 Correct 109 ms 240240 KB Output is correct
26 Correct 109 ms 240204 KB Output is correct
27 Correct 109 ms 240136 KB Output is correct
28 Correct 114 ms 240860 KB Output is correct
29 Correct 120 ms 242508 KB Output is correct
30 Correct 109 ms 240584 KB Output is correct
31 Correct 113 ms 241228 KB Output is correct
32 Correct 114 ms 240904 KB Output is correct
33 Correct 128 ms 245120 KB Output is correct
34 Correct 146 ms 245048 KB Output is correct
35 Correct 132 ms 244752 KB Output is correct
36 Correct 109 ms 240664 KB Output is correct
37 Correct 124 ms 247884 KB Output is correct
38 Correct 135 ms 247524 KB Output is correct
39 Correct 128 ms 247536 KB Output is correct
40 Correct 133 ms 247600 KB Output is correct
41 Correct 129 ms 247616 KB Output is correct
42 Correct 113 ms 240880 KB Output is correct
43 Correct 117 ms 240844 KB Output is correct
44 Correct 128 ms 240764 KB Output is correct
45 Correct 223 ms 261492 KB Output is correct
46 Correct 200 ms 261492 KB Output is correct
47 Runtime error 136 ms 262144 KB Execution killed with signal 9
48 Halted 0 ms 0 KB -