oj.uz

Submission #722007

# Submission time Handle Problem Language Result Execution time Memory
722007 2023-04-11T10:23:52 Z n0sk1ll Jakarta Skyscrapers (APIO15_skyscraper) C++14
10 / 100
 141 ms 236076 KB 
#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
//const int mod = 1000000007;







//Note to self: Check for overflow

vector<pii> g[30003];
bool vis[30003];

int km=0; const int sf=5000000;
vector<int> dat[2*sf+15];

int main()
{
    FAST;

    int n,m; cin>>n>>m;
    set<pii> doges;

    int s,t;
    ff(i,0,m)
    {
        int b,p; cin>>b>>p;
        doges.insert({b,p});
        if (i==0) s=b;
        if (i==1) t=b;
    }

    for (auto [b,p] : doges)
    {
        for (int i=1;;i++)
        {
            if (b+i*p>=n) break;
            g[b].pb({b+i*p,i});
        }
        for (int i=1;;i++)
        {
            if (b-i*p<0) break;
            g[b].pb({b-i*p,i});
        }
    }

    dat[0].pb(s);
    fff(d,0,n+2)
    {
        if (d>=(km+1)*sf)
        {
            ff(i,0,sf) dat[i]=dat[i+sf],dat[i+sf].clear();
            km++;
        }
        for (auto p : dat[d-km*sf])
        {
            if (vis[p]) continue; vis[p]=1;
            if (p==t) return cout<<d,0;
            for (auto it : g[p]) dat[d+it.yy-km*sf].pb(it.xx);
        }
        dat[d-km*sf].clear();
    }

    cout<<-1;
}

//Note to self: Check for overflow

/*

5 3
0 2
1 1
4 1

*/

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:59:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |     for (auto [b,p] : doges)
      |               ^
skyscraper.cpp:83:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   83 |             if (vis[p]) continue; vis[p]=1;
      |             ^~
skyscraper.cpp:83:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   83 |             if (vis[p]) continue; vis[p]=1;
      |                                   ^~~
skyscraper.cpp:84:13: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
   84 |             if (p==t) return cout<<d,0;
      |             ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 235784 KB Output is correct
2 Correct 114 ms 235792 KB Output is correct
3 Correct 114 ms 235768 KB Output is correct
4 Correct 111 ms 235768 KB Output is correct
5 Correct 120 ms 235816 KB Output is correct
6 Correct 124 ms 235760 KB Output is correct
7 Correct 133 ms 235744 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 235736 KB Output is correct
2 Correct 121 ms 235840 KB Output is correct
3 Correct 126 ms 235772 KB Output is correct
4 Correct 108 ms 235724 KB Output is correct
5 Correct 118 ms 235924 KB Output is correct
6 Correct 128 ms 235832 KB Output is correct
7 Correct 127 ms 236028 KB Output is correct
8 Correct 110 ms 235752 KB Output is correct
9 Correct 117 ms 235848 KB Output is correct
10 Correct 128 ms 235884 KB Output is correct
11 Correct 141 ms 236012 KB Output is correct
12 Incorrect 125 ms 235856 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 235796 KB Output is correct
2 Correct 118 ms 235828 KB Output is correct
3 Correct 114 ms 235844 KB Output is correct
4 Correct 120 ms 235840 KB Output is correct
5 Correct 116 ms 235756 KB Output is correct
6 Correct 111 ms 235784 KB Output is correct
7 Correct 110 ms 235780 KB Output is correct
8 Correct 116 ms 235760 KB Output is correct
9 Correct 122 ms 235828 KB Output is correct
10 Correct 116 ms 235844 KB Output is correct
11 Correct 114 ms 235968 KB Output is correct
12 Incorrect 134 ms 235836 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 235736 KB Output is correct
2 Correct 115 ms 235844 KB Output is correct
3 Correct 131 ms 235784 KB Output is correct
4 Correct 120 ms 235828 KB Output is correct
5 Correct 112 ms 235744 KB Output is correct
6 Correct 114 ms 235872 KB Output is correct
7 Correct 123 ms 235916 KB Output is correct
8 Correct 119 ms 235912 KB Output is correct
9 Correct 110 ms 235840 KB Output is correct
10 Correct 113 ms 235884 KB Output is correct
11 Correct 124 ms 235940 KB Output is correct
12 Incorrect 125 ms 235760 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 235912 KB Output is correct
2 Correct 116 ms 235948 KB Output is correct
3 Correct 121 ms 235800 KB Output is correct
4 Correct 123 ms 235856 KB Output is correct
5 Correct 117 ms 235912 KB Output is correct
6 Correct 135 ms 235840 KB Output is correct
7 Correct 113 ms 235828 KB Output is correct
8 Correct 109 ms 235776 KB Output is correct
9 Correct 111 ms 235788 KB Output is correct
10 Correct 128 ms 235772 KB Output is correct
11 Correct 118 ms 236076 KB Output is correct
12 Incorrect 118 ms 235808 KB Output isn't correct
13 Halted 0 ms 0 KB -