oj.uz

Submission #838446

# Submission time Handle Problem Language Result Execution time Memory
838446 2023-08-27T00:55:50 Z 8pete8 Jakarta Skyscrapers (APIO15_skyscraper) C++14
10 / 100
 64 ms 133776 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define pb push_back
#define all(x) x.begin(),x.end()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define p push
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
const int mxn=3*1e4,mod=998244353,lg=42,root=80,inf=1e9;
void setIO(string name) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}
int dist[(2*mxn*(root+1))+10];
vector<pii>adj[(2*mxn*(root+1))+10];
bitset<(2*mxn*(root+1))+10>vis;
int n,m;
//make dummy node
// n orginal + n node for each root(n)
//node more than root id = mxn*ith+starting point
void init(){
    for(int i=1;i<=min(n,root);i++){
        for(int j=0;j<n;j++){
            adj[(mxn*i)+j].pb({j,0});//going down
        }
        for(int j=i;j<n;j++){
            //buid=ld edge for each i
            adj[(mxn*i)+j].pb({(mxn*i)+(j-i),1});
            adj[(mxn*i)+(j-i)].pb({(mxn*i)+j,1});
        }
    }
}
int32_t main(){
    fastio
    cin>>n>>m;
    int end;
    init();
    fill(dist,dist+(2*mxn*(root+1)),inf);
    priority_queue<pii,vector<pii>,greater<pii>>pq;
    for(int i=0;i<m;i++){
        int st,p;cin>>st>>p;
        if(i==1)end=st;
        if(i==0)pq.push({0,st}),dist[st]=0;
        if(p<=root)adj[st].pb({(p*mxn)+st,0});
        else{
            for(int j=1;(j*p)+st<n;j++){
                adj[st].pb({(j*p)+st,j});
                adj[(j*p)+st].pb({st,j});
            }
            for(int j=1;st-(j*p)>=0;j++){
                adj[st].pb({st-(j*p),j});
                adj[st-(j*p)].pb({st,j});
            }
            //connect normal edge
        }
        //input
    }
    //dijkstra
    while(!pq.empty()){
        int cur=pq.top().s;
        pq.pop();
        for(auto i:adj[cur]){
            if(dist[i.f]>dist[cur]+i.s){
                dist[i.f]=dist[cur]+i.s;
                pq.push({dist[i.f],i.f});
            }
        }
    }
    cout<<((dist[end]==inf)?-1:dist[end]);
    return 0;
}

Compilation message

skyscraper.cpp: In function 'void setIO(std::string)':
skyscraper.cpp:31:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:32:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp: In function 'int32_t main()':
skyscraper.cpp:89:21: warning: 'end' may be used uninitialized in this function [-Wmaybe-uninitialized]
   89 |     cout<<((dist[end]==inf)?-1:dist[end]);
      |             ~~~~~~~~^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 133416 KB Output is correct
2 Correct 57 ms 133412 KB Output is correct
3 Correct 54 ms 133368 KB Output is correct
4 Correct 56 ms 133396 KB Output is correct
5 Correct 54 ms 133452 KB Output is correct
6 Correct 64 ms 133468 KB Output is correct
7 Correct 54 ms 133408 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 133460 KB Output is correct
2 Correct 54 ms 133460 KB Output is correct
3 Correct 56 ms 133364 KB Output is correct
4 Correct 56 ms 133396 KB Output is correct
5 Correct 56 ms 133344 KB Output is correct
6 Correct 58 ms 133460 KB Output is correct
7 Correct 56 ms 133512 KB Output is correct
8 Correct 61 ms 133504 KB Output is correct
9 Correct 56 ms 133528 KB Output is correct
10 Correct 59 ms 133708 KB Output is correct
11 Correct 57 ms 133688 KB Output is correct
12 Incorrect 56 ms 133684 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 133444 KB Output is correct
2 Correct 56 ms 133428 KB Output is correct
3 Correct 57 ms 133384 KB Output is correct
4 Correct 56 ms 133424 KB Output is correct
5 Correct 56 ms 133456 KB Output is correct
6 Correct 57 ms 133380 KB Output is correct
7 Correct 56 ms 133460 KB Output is correct
8 Correct 57 ms 133460 KB Output is correct
9 Correct 58 ms 133528 KB Output is correct
10 Correct 57 ms 133672 KB Output is correct
11 Correct 58 ms 133724 KB Output is correct
12 Incorrect 58 ms 133776 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 133460 KB Output is correct
2 Correct 56 ms 133444 KB Output is correct
3 Correct 56 ms 133376 KB Output is correct
4 Correct 56 ms 133352 KB Output is correct
5 Correct 57 ms 133408 KB Output is correct
6 Correct 58 ms 133456 KB Output is correct
7 Correct 56 ms 133460 KB Output is correct
8 Correct 59 ms 133504 KB Output is correct
9 Correct 56 ms 133580 KB Output is correct
10 Correct 58 ms 133764 KB Output is correct
11 Correct 58 ms 133744 KB Output is correct
12 Incorrect 57 ms 133688 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 133472 KB Output is correct
2 Correct 58 ms 133360 KB Output is correct
3 Correct 57 ms 133432 KB Output is correct
4 Correct 55 ms 133412 KB Output is correct
5 Correct 59 ms 133460 KB Output is correct
6 Correct 59 ms 133452 KB Output is correct
7 Correct 56 ms 133432 KB Output is correct
8 Correct 59 ms 133388 KB Output is correct
9 Correct 56 ms 133580 KB Output is correct
10 Correct 58 ms 133708 KB Output is correct
11 Correct 58 ms 133732 KB Output is correct
12 Incorrect 58 ms 133776 KB Output isn't correct
13 Halted 0 ms 0 KB -