oj.uz

Submission #247130

# Submission time Handle Problem Language Result Execution time Memory
247130 2020-07-11T06:30:48 Z rrrr10000 Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 59 ms 16256 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
#define dame(a) {out(a);return 0;}
#define decimal cout<<fixed<<setprecision(15);
#define dupli(a) a.erase(unique(all(a)),a.end())
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef tuple<ll,ll,ll,ll> PPP;
typedef multiset<ll> S;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vvvvi=vector<vvvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=1001001001001001001;
const ll INF=1001001001;
const ll mod=1000000007;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void noyes(T b){if(b)out("no");else out("yes");}
template<class T> void NoYes(T b){if(b)out("No");else out("Yes");}
template<class T> void NOYES(T b){if(b)out("NO");else out("YES");}
void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll modpow(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll k=1000;
int main(){
    ll n,m;cin>>n>>m;
    vvi v(n);
    ll s,g;
    rep(i,m){
        ll a,b;cin>>a>>b;
        if(i==0)s=a;
        if(i==1)g=a;
        v[a].pb(b);
    }
    vvi dis(n,vi(k+1,inf));
    SPQ(PP) pq;
    dis[s][0]=0;
    pq.emplace(0,s,0);
    while(!pq.empty()){
        auto t=pq.top();pq.pop();
        ll cost,i,j;
        tie(cost,i,j)=t;
        if(i==g)dame(cost);
        if(dis[i][j]!=cost)continue;
        if(j){
            if(i+j<n)if(chmin(dis[i+j][j],cost+1))pq.emplace(cost+1,i+j,j);
            if(i-j>=0)if(chmin(dis[i-j][j],cost+1))pq.emplace(cost+1,i-j,j);
            if(chmin(dis[i][0],cost))pq.emplace(cost,i,0);
        }
        else{
            for(ll x:v[i]){
                if(x<=k)if(chmin(dis[i][x],cost))pq.emplace(cost,i,x);
                else{
                    for(ll u=1;u*x+i<n;u++)if(chmin(dis[u*x+i][0],cost+u))pq.emplace(cost+u,u*x+i,0);
                    for(ll u=-1;u*x+i>=0;u--)if(chmin(dis[u*x+i][0],cost-u))pq.emplace(cost-u,u*x+i,0);
                }
            }
        }
    }
    out(-1);
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:81:19: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
                 if(x<=k)if(chmin(dis[i][x],cost))pq.emplace(cost,i,x);
                   ^
skyscraper.cpp:72:9: warning: 'g' may be used uninitialized in this function [-Wmaybe-uninitialized]
         if(i==g)dame(cost);
         ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 5 ms 1152 KB Output is correct
11 Correct 6 ms 1152 KB Output is correct
12 Correct 6 ms 1152 KB Output is correct
13 Correct 6 ms 1152 KB Output is correct
14 Correct 7 ms 1280 KB Output is correct
15 Correct 7 ms 1152 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 416 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 5 ms 1152 KB Output is correct
11 Correct 6 ms 1152 KB Output is correct
12 Correct 6 ms 1152 KB Output is correct
13 Correct 6 ms 1152 KB Output is correct
14 Correct 7 ms 1152 KB Output is correct
15 Correct 7 ms 1152 KB Output is correct
16 Correct 6 ms 1920 KB Output is correct
17 Correct 10 ms 6272 KB Output is correct
18 Correct 15 ms 14208 KB Output is correct
19 Correct 13 ms 16128 KB Output is correct
20 Correct 59 ms 16256 KB Output is correct
21 Correct 7 ms 3456 KB Output is correct
22 Correct 13 ms 14464 KB Output is correct
23 Incorrect 17 ms 12928 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 5 ms 1152 KB Output is correct
11 Correct 6 ms 1152 KB Output is correct
12 Correct 6 ms 1152 KB Output is correct
13 Correct 6 ms 1152 KB Output is correct
14 Correct 7 ms 1280 KB Output is correct
15 Correct 7 ms 1152 KB Output is correct
16 Correct 6 ms 1920 KB Output is correct
17 Correct 10 ms 6272 KB Output is correct
18 Correct 12 ms 14208 KB Output is correct
19 Correct 13 ms 16128 KB Output is correct
20 Correct 58 ms 16256 KB Output is correct
21 Correct 7 ms 3456 KB Output is correct
22 Correct 12 ms 14336 KB Output is correct
23 Incorrect 13 ms 13056 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 5 ms 1152 KB Output is correct
11 Correct 7 ms 1152 KB Output is correct
12 Correct 6 ms 1152 KB Output is correct
13 Correct 6 ms 1152 KB Output is correct
14 Correct 7 ms 1152 KB Output is correct
15 Correct 6 ms 1152 KB Output is correct
16 Correct 6 ms 1920 KB Output is correct
17 Correct 9 ms 6272 KB Output is correct
18 Correct 12 ms 14080 KB Output is correct
19 Correct 14 ms 16128 KB Output is correct
20 Correct 58 ms 16256 KB Output is correct
21 Correct 8 ms 3456 KB Output is correct
22 Correct 13 ms 14464 KB Output is correct
23 Incorrect 13 ms 12928 KB Output isn't correct
24 Halted 0 ms 0 KB -