Submission #1110699

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110699		minhquaanz	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	52 ms	12996 KiB

skyscraper

/*Code by TMQ*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define ii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define em emplace
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define FIV(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define all(x) (x).begin(), (x).end()
#define reset(a, x) (memset(a, x, sizeof(a)));
#define testcase \
    int tc;      \
    cin >> tc;   \
    while (tc--) \
        solve();
#define howlong cerr << "Time elapsed: " << fixed << setprecision(9) << (double)clock() / CLOCKS_PER_SEC << "s";
#define what_is(x) cerr << #x << " is " << x << '\n';
ll inline GCD(ll a, ll b) { return !b ? abs(a) : GCD(b, a % b); }
ll inline LCM(ll a, ll b) { return (a / GCD(a, b) * b); }
template <class X, class Y>
bool maximize(X &x, Y y)
{
    if (x < y)
    {
        x = y;
        return true;
    }
    return false;
};
template <class X, class Y>
bool minimize(X &x, Y y)
{
    if (x > y)
    {
        x = y;
        return true;
    }
    return false;
};
///=====================================s========================================
#define BIT(i, mask) ((mask >> (i)) & 1)
#define DAOBIT(i, mask) ((mask ^ (1 << i)))
#define OFFBIT(i, mask) ((mask & ~(1 << (i))))
#define ONBIT(i, mask) ((mask | (1 << (i))))
///============================================================================
const ll mod = 1e9 + 7;
const ll inf = (ll)1e18 + 10;
const ll nmax = 5e4 + 5;
const ll B = 230;
///============================================================================
void TASK(string task)
{
    if (fopen((task + ".inp").c_str(), "r"))
    {
        freopen((task + ".inp").c_str(), "r", stdin);
        freopen((task + ".out").c_str(), "w", stdout);
    }
}
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template <typename T, typename V>
void __print(const pair<T, V> &x)
{
    cerr << '{';
    __print(x.first);
    cerr << ',';
    __print(x.second);
    cerr << '}';
}
template <typename T>
void __print(const T &x)
{
    int f = 0;
    cerr << '{';
    for (auto &i : x)
        cerr << (f++ ? "," : ""), __print(i);
    cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v)
{
    __print(t);
    if (sizeof...(v))
        cerr << ", ";
    _print(v...);
}
#ifndef ONLINE_JUDGE
#define debug(x...)                   \
    {                                 \
        cerr << "[" << #x << "] = ["; \
        _print(x);                    \
    }
#else
#define debug(x...)
#endif
///============================================================================
int n, m, b[nmax], p[nmax];
vector<vector<int>> doge;
bool check[nmax][B];
int dp[nmax];
///============================================================================
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    TASK("name");
    cin >> n >> m;
    doge.resize(n + 1);
    for (int i = 0; i < m; i++)
    {
        cin >> b[i] >> p[i];
        doge[b[i]].push_back(p[i]);
        if (p[i] < B)
        {
            check[b[i]][p[i]] = true;
        }
    }
    reset(dp, 0x3f);
    ll max_val = dp[0];
    dp[b[0]] = 0;
    priority_queue<ii, vector<ii>, greater<ii>> pq;
    pq.push({0, b[0]});
    while (!pq.empty())
    {
        int v = pq.top().second;
        int d = pq.top().first;
        pq.pop();
        if (dp[v] != d)
            continue;
        if (v == b[1])
            break;
        for (int k = 0; k < doge[v].size(); k++)
        {
            int p = doge[v][k];
            for (int i = v + p; i < n; i += p)
            {
                if (dp[i] > dp[v] + (i - v) / p)
                {
                    dp[i] = dp[v] + (i - v) / p;
                    pq.push({dp[i], i});
                }
                if (p < B && check[i][p])
                    break;
                if (p < B)
                    check[i][p] = 1;
            }
            for (int i = v - p; i >= 0; i -= p)
            {
                if (dp[i] > dp[v] + (v - i) / p)
                {
                    dp[i] = dp[v] + (v - i) / p;
                    pq.push({dp[i], i});
                }
                if (p < B && check[i][p])
                    break;
                if (p < B)
                    check[i][p] = 1;
            }
        }
    }
    cout << (dp[b[1]] == max_val ? -1 : dp[b[1]]);
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:152:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |         for (int k = 0; k < doge[v].size(); k++)
      |                         ~~^~~~~~~~~~~~~~~~
skyscraper.cpp: In function 'void TASK(std::string)':
skyscraper.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen((task + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen((task + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 43 / 43