Submission #143427

#	Time	Username	Problem	Language	Result	Execution time	Memory
143427		EntityIT	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1027 ms	37168 KiB

skyscraper

#include<bits/stdc++.h>

using namespace std;

int n, m;
vector<int> b, p;
vector< set<int> > setP;
vector< map<int, int> > dp;

int main() {
    scanf("%d %d", &n, &m);
    b.assign(m, 0);
    p.assign(m, 0);
    setP.assign(n, set<int>() );
    for (int i = 0; i < m; ++i) {
        scanf("%d %d", &b[i], &p[i]);
        setP[ b[i] ].insert(p[i]);
    }

    dp.assign(n, map<int, int>() );

    priority_queue< pair<int, pair<int, int> >,
                    vector< pair<int, pair<int, int> > >,
                    greater< pair<int, pair<int, int> > > > pq;
    dp[ b[0] ][ p[0] ] = 0; pq.push( { dp[ b[0] ][ p[0] ], { b[0], p[0] } } );

    while (!pq.empty() ) {
        auto tmp = pq.top(); pq.pop();

        int curPos = tmp.second.first,
            curPow = tmp.second.second;

        if (tmp.first > dp[curPos][curPow]) continue;

        for (int pow : setP[curPos]) {
            if (!dp[curPos].count(pow) || dp[curPos][pow] > dp[curPos][curPow]) {
                dp[curPos][pow] = dp[curPos][curPow];
                pq.push( { dp[curPos][pow], { curPos, pow } } );
            }
        }
        setP[curPos].clear();

        if (curPos + curPow < n &&
            (!dp[curPos + curPow].count(curPow) || dp[curPos + curPow][curPow] > dp[curPos][curPow] + 1) ) {
            dp[curPos + curPow][curPow] = dp[curPos][curPow] + 1;
            pq.push( { dp[curPos + curPow][curPow], { curPos + curPow, curPow } } );
        }

        if (curPos - curPow >= 0 &&
            (!dp[curPos - curPow].count(curPow) || dp[curPos - curPow][curPow] > dp[curPos][curPow] + 1) ) {
            dp[curPos - curPow][curPow] = dp[curPos][curPow] + 1;
            pq.push( { dp[curPos - curPow][curPow], { curPos - curPow, curPow } } );
        }
    }

    if (!dp[ b[1] ].count(p[1]) ) printf("-1\n");
    else printf("%d\n", dp[ b[1] ][ p[1] ]);

    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &b[i], &p[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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