제출 #554488

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
554488		josanneo22	Jakarta Skyscrapers (APIO15_skyscraper)	C++11	0 / 100	1 ms	980 KiB

skyscraper

#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<stdlib.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pair<int, int> > vpii;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b); i > (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define mp make_pair
#define pb push_back
#define rsz resize
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define f first
#define s second
#define out(x) cout<<x;
#define in(x) cin>>x;
#define inarr(a,x,y) for(int i=x;i<y;i++){cin>>a[i];}
#define incor(a,x,y) for(int i=x;i<y;i++){cin>>a[i].f>>a[i].s;}
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
const int mod = 1e9 + 7;

void file_in(string s)
{
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
void normal()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
}
ll ex(int base, int power)
{
    if (power == 0)
        return 1;
    ll result = ex(base, power / 2);
    if (power % 2 == 1)
        return(((result * result) % mod) * base) % mod;
    else return (result * result) % mod;
}

const int maxn = 30005;
int dist[maxn], B[maxn], P[maxn];
vi powers[maxn];
int n, m;

void solve(int s)
{
    priority_queue<pii, vector<pii>, greater<pii> > q;
    q.push(mp(dist[s], s));// first is distance, second is position
    pii t;
    while (!q.empty())
    {
        t = q.top(); q.pop();
        if (t.f > dist[t.s]) continue;// we only need to find minimum distance, then if already greater than, no need to continue these values;
        trav(p, powers[t.s])//powers
        {
            for (int x = 1;t.s + p * x < n;++x)
            {
                int pos = t.s + p * x;
                if (dist[pos] > t.f + x)
                {
                    dist[pos] = t.f + x;//keep updating minimum
                    q.push(mp(dist[pos], pos));
                    if (binary_search(all(powers[pos]), p)) break;//if there is a power there so no need to continue the other path
                }
            }
            for (int x = 1;t.s - p * x >= 0;++x)//duplicate but -p instead of +p
            {
                int pos = t.s - p * x;
                if (dist[pos] > t.f + x)//note that distance always increases
                {
                    dist[pos] = t.f + x;
                    q.push(mp(dist[pos], pos));
                    if (binary_search(all(powers[pos]), p)) break;
                }
            }
        }
    }
}
int main()
{
    normal();

    cin >> n >> m;
    vi temp;
    FOR(i, 0, m)
    {
        cin >> B[i] >> P[i];
        powers[B[i]].pb(P[i]);
        temp.pb(B[i]);
    }
    FOR(i, 0, temp.size())
    {
        sort(all(powers[temp[i]]));
        powers[temp[i]].erase(unique(all(powers[temp[i]])), powers[temp[i]].end());//erase duplicates
    }
    memset(dist, (int)1e9, maxn);
    dist[B[0]] = 0;
    solve(B[0]);
    if (dist[B[1]] == 1e9) cout << "-1";
    else cout << dist[B[1]];
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:14:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
      |                                        ^
skyscraper.cpp:105:5: note: in expansion of macro 'FOR'
  105 |     FOR(i, 0, temp.size())
      |     ^~~
skyscraper.cpp:110:32: warning: 'memset' used with length equal to number of elements without multiplication by element size [-Wmemset-elt-size]
  110 |     memset(dist, (int)1e9, maxn);
      |                                ^
skyscraper.cpp: In function 'void file_in(std::string)':
skyscraper.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:38:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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