oj.uz

답안 #1059011

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1059011 2024-08-14T15:59:34 Z sammyuri Jakarta Skyscrapers (APIO15_skyscraper) C++17
10 / 100
 1 ms 6748 KB 
#include <bits/stdc++.h>
using namespace std;

/*
we run dijkstra
let B = 100
for all doges that have p >= b, just simulate the jumps
how do we deal with the "small" doges??
note that the answer is never more than 30000...
*/

const int SMALL = 100;
const int MAXN = 30000;
const int INF = 1e9;
int mintime[MAXN][SMALL + 1];
int dist[MAXN];
vector<int> doges[MAXN];
bitset<MAXN> todo[MAXN + 1];

int main() {
    int n; cin >> n;
    int m; cin >> m;
    for (int i = 0; i < n; i ++)
        for (int j = 1; j <= SMALL; j ++)
            mintime[i][j] = INF;
    for (int i = 0; i < n; i ++)
        dist[i] = INF;
    int startnode = -1, target = -1;
    for (int i = 0; i < m; i ++) {
        int b, p; cin >> b >> p;
        if (i == 0)
            startnode = b;
        else if (i == 1)
            target = b;
        doges[b].push_back(p);
    }
    if (startnode == target) {
        cout << 0 << endl; return 0;
    }
    todo[0][startnode] = 1;
    dist[startnode] = 0;
    bool done = false;
    for (int t = 0; t <= n; t ++) {
        while (true) {
            int xx = todo[t]._Find_first();
            if (xx == MAXN) break;
            todo[t][xx] = false;
            int curnode = xx;
            for (auto doge : doges[curnode]) {
                // big doge
                if (doge > SMALL) {
                    int extratime = 0;
                    for (int j = curnode - doge; j >= 0; j -= doge) {
                        extratime ++;
                        if (dist[j] > extratime + t) {
                            if (dist[j] != INF)
                                todo[dist[j]][j] = 0;
                            dist[j] = extratime + t;
                            todo[dist[j]][j] = 1;
                        }
                    }
                    extratime = 0;
                    for (int j = curnode + doge; j < n; j += doge) {
                        extratime ++;
                        if (dist[j] > extratime + t) {
                            if (dist[j] != INF)
                                todo[dist[j]][j] = 0;
                            dist[j] = extratime + t;
                            todo[dist[j]][j] = 1;
                        }
                    }
                }
                // small doge
                else {
                    // ignore entirely
                    if (mintime[curnode][doge] <= t)
                        continue;
                    mintime[curnode][doge] = t;
                    int extratime = 0;
                    for (int j = curnode - doge; j >= 0; j -= doge) {
                        extratime ++;
                        // stop
                        if (mintime[j][doge] <= t + extratime)
                            break;
                        mintime[j][doge] = t + extratime;
                        if (dist[j] > extratime + t) {
                            if (dist[j] != INF)
                                todo[dist[j]][j] = 0;
                            dist[j] = extratime + t;
                            todo[dist[j]][j] = 1;
                        }
                    }
                    extratime = 0;
                    for (int j = curnode + doge; j < n; j += doge) {
                        extratime ++;
                        // stop
                        if (mintime[j][doge] <= t + extratime)
                            break;
                        mintime[j][doge] = t + extratime;
                        if (dist[j] > extratime + t) {
                            if (dist[j] != INF)
                                todo[dist[j]][j] = 0;
                            dist[j] = extratime + t;
                            todo[dist[j]][j] = 1;
                        }
                    }
                }
            }
            if (curnode == target) {
                done = true; break;
            }
        }
        if (done) break;
    }
    if (dist[target] == INF) {
        cout << -1 << endl;
    } else cout << dist[target] << endl;
    return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 0 ms 1116 KB Output is correct
7 Correct 0 ms 1116 KB Output is correct

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 1116 KB Output is correct
4 Correct 0 ms 1116 KB Output is correct
5 Correct 0 ms 2392 KB Output is correct
6 Correct 0 ms 2392 KB Output is correct
7 Correct 0 ms 1116 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 1116 KB Output is correct
10 Correct 1 ms 1372 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Incorrect 1 ms 6748 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 1116 KB Output is correct
6 Correct 0 ms 1116 KB Output is correct
7 Correct 0 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 1 ms 1372 KB Output is correct
11 Correct 1 ms 1372 KB Output is correct
12 Incorrect 1 ms 4700 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 1116 KB Output is correct
6 Correct 0 ms 1116 KB Output is correct
7 Correct 0 ms 1116 KB Output is correct
8 Correct 0 ms 2484 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 1372 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Incorrect 1 ms 1372 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 1116 KB Output is correct
3 Correct 1 ms 1160 KB Output is correct
4 Correct 0 ms 1116 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 1116 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Incorrect 1 ms 6748 KB Output isn't correct
13 Halted 0 ms 0 KB -