oj.uz

Submission #40056

# Submission time Handle Problem Language Result Execution time Memory
40056 2018-01-26T07:45:32 Z ztrong Jakarta Skyscrapers (APIO15_skyscraper) C++14
0 / 100
 1 ms 237680 KB 
#include <bits/stdc++.h>
#define llint long long
#define fi first
#define se second
#define BIT(x, i) ((x>>i)&1ll)
#define MASK(i) (1ll<<i)
#define db(x) cout << #x << " = " << x << endl;
using namespace std;

void openFile() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
#ifdef Tr___
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
#else
    //freopen("tname.inp", "r", stdin);
    //freopen("tname.out", "w", stdout);
#endif
}
template <typename T>
inline void read(T &ret){
	register char c = getchar(); bool neg = false; ret = 0;
	while (c < '0' || c > '9'){ if (c == '-') neg = true; c = getchar(); }
	while (c >= '0' && c <= '9'){ ret = (ret << 1) + (ret << 3) + c - '0'; 
        c = getchar(); }
	if (neg) ret = -ret;
}

template <typename T>
void write(T x){
	if (x < 0){ putchar('-'); x = -x; }
	if (x >= 10) write(x / 10); putchar(x % 10 + 48);
}

const int maxn = 3e4 + 5;
const int maxm = 1e6 + 5;
const llint inf = 1e9 + 7;
const int maxk = 2000;

int N, M;
int b[maxn], p[maxn];
vector<int> vertex[maxn];
int edge[maxn][maxk];
queue<int> q;
bool inq[maxn];
int d[maxn];

void enter() {
    read(N); read(M);
    for (int i = 1; i <= M; ++i) {
        read(b[i]); read(p[i]);
        //if (p[i] < maxk) {
        //    if (!edge[b[i]][p[i]]) {
        //        edge[b[i]][p[i]] = true;
        //        for (int j = b[i]; j >= 1; j -= p[i]) {
        //            edge[j][p[i]] = true;
        //        }
        //        for (int j = b[i]; j <= N; j += p[i]) {
        //            edge[j][p[i]] = true;
        //        }
        //    }
        //}
        //else {
            vertex[b[i]].push_back(p[i]);
        //}
    }
}

void solve() {
    fill_n(d, maxn, inf);
    d[0] = 0;
    inq[0] = true;
    q.push(0);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        inq[u] = false;
        for (int k = 1; k < maxk; ++k) {
            if (edge[u][k]) {
                int v = u + k;
                if (v <= N && d[v] > d[u] + 1) {
                    d[v] = d[u] + 1;
                    if (!inq[v]) {
                        q.push(v);
                        inq[v] = true;
                    }
                }

                v = u - k;
                if (v >= 1 && d[v] > d[u] + 1) {
                    d[v] = d[u] + 1;
                    if (!inq[v]) {
                        q.push(v);
                        inq[v] = true;
                    }
                }
            }
        }

        for (auto k : vertex[u]) {
            for (int j = u; j <= N; j += k) {
                if (d[j] > d[u] + (j - u) / k) {
                    d[j] = d[u] + (j - u) / k;
                    if (!inq[j]) {
                        q.push(j);
                        inq[j] = true;
                    }
                }
            }
            for (int j = u; j >= 1; j -= k) {
                if (d[j] > d[u] + (u - j) / k) {
                    d[j] = d[u] + (u - j) / k;
                    if (!inq[j]) {
                        q.push(j);
                        inq[j] = true;
                    }
                }
            }
        }
    }

    if (d[1] == inf) d[1] = -1;
    cout << d[1] << endl;
}

int main() {
    openFile();
    enter();
    solve();
    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 43.0

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