oj.uz

답안 #873772

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
873772 2023-11-15T17:34:50 Z thienhx Palembang Bridges (APIO15_bridge) C++17
0 / 100
 7 ms 54620 KB 
#include <bits/stdc++.h>
using namespace std;

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using str = string;
using ld = long double;
using db = double;

///--------------------------------

#define           F   first
#define           S   second
#define          pb   push_back
#define          lb   lower_bound
#define          ub   upper_bound
#define       sz(x)   (int)((x).size())
#define      all(x)   (x).begin(), (x).end()
#define     rall(x)   (x).rbegin(), (x).rend()
#define   mem(f, x)   memset(f, x, sizeof(f))
#define  uniqueV(x)   sort(all(x)), (x).resize(unique(all(x)) - x.begin())

template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }

///--------------------------------

#define PROBLEM "test"

const int MOD = 1e9 + 7; // 998244353;
const ll INF = 1e18;
const ld eps = 1e-9;
const ld PI = acos(-1);
const int dx[4]{0, 1, 0, -1}, dy[4]{1, 0, -1, 0}; // R D L U
const int ddx[4]{-1, 1, 1, -1}, ddy[4]{1, 1, -1, -1}; // UR DR DL UL

///--------------------------------

void precalc();
void solve();

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    if (fopen(PROBLEM".inp", "r")) {
        freopen(PROBLEM".inp", "r", stdin);
        freopen(PROBLEM".out", "w", stdout);
    }

    constexpr bool MULTI_TEST = 0;

    int t = 1;
    if (MULTI_TEST) cin >> t;

    while (t--)
        solve();
    
    // cerr << setprecision(3) << fixed;
    // cerr << "[" << 1.0 * clock() / CLOCKS_PER_SEC << "s]  ";
}

///--------------------[PROBLEM SOLUTION]--------------------///

const int BLOCKSZ = 200;
const int maxn = 30030;
ll dist[maxn][BLOCKSZ + 1];
bool vis[maxn][BLOCKSZ + 1];
vector<ll> spec[maxn];
ll n, m, P[maxn], B[maxn];

void solve() {
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        cin >> B[i] >> P[i];

        spec[B[i]].pb(P[i]);
    }

    mem(dist, 0x3f);
    mem(vis, false);
    priority_queue<array<ll, 3>, vector<array<ll, 3>>, greater<array<ll, 3>>> pq;

    auto addHeavy = [&](int x, int y, ll D) -> void {
        for (int nx = x % y; nx < n; nx += y) {
            if (!vis[nx][BLOCKSZ]  && minimize(dist[nx][BLOCKSZ], D + abs(nx - x) / y))
                pq.push({dist[nx][BLOCKSZ], nx, BLOCKSZ});
        }
    };

    if (P[0] >= BLOCKSZ)
        addHeavy(B[0], P[0], 0);

    dist[B[0]][BLOCKSZ] = 0;
    pq.push({0, B[0], BLOCKSZ});

    while (pq.size()) {
        int x = pq.top()[1], y = pq.top()[2]; pq.pop();    

        if (vis[x][y]) continue;
        
        vis[x][y] = true;
        if (y == BLOCKSZ) {
            for (ll cy : spec[x]) {
                if (cy < BLOCKSZ) {
                    if (!vis[x][cy] && minimize(dist[x][cy], dist[x][y]))
                        pq.push({dist[x][cy], x, cy});
                }
                else addHeavy(x, cy, dist[x][BLOCKSZ]);
            }
            spec[x].clear();

            continue;
        }

        //dummy vertex
        if (x - y >= 0 && !vis[x -  y][BLOCKSZ]
                 && minimize(dist[x - y][BLOCKSZ], dist[x][y] + 1))
            pq.push({dist[x - y][BLOCKSZ], x - y, BLOCKSZ});
        if (x + y < n && !vis[x + y][BLOCKSZ]
                 && minimize(dist[x + y][BLOCKSZ], dist[x][y] + 1))
            pq.push({dist[x + y][BLOCKSZ], x + y, BLOCKSZ});

        //direct path
        if (x - y >= 0 && !vis[x -  y][y]
                 && minimize(dist[x - y][y], dist[x][y] + 1))
            pq.push({dist[x - y][y], x - y, y});
        if (x + y < n && !vis[x + y][y]
                 && minimize(dist[x + y][y], dist[x][y] + 1))
            pq.push({dist[x + y][y], x + y, y});
    }

    cout << (!vis[B[1]][BLOCKSZ] ? -1 : dist[B[1]][BLOCKSZ]) << '\n';
}

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         freopen(PROBLEM".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         freopen(PROBLEM".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 54616 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 54620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 54364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 54616 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 54616 KB Output isn't correct
2 Halted 0 ms 0 KB -