Submission #243387

#TimeUsernameProblemLanguageResultExecution timeMemory
243387NaimSSJakarta Skyscrapers (APIO15_skyscraper)C++14
22 / 100
27 ms25088 KiB
#include <bits/stdc++.h> #define ld long double #define endl "\n" #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define pb(x) push_back(x) #define mp(a,b) make_pair(a,b) #define ms(v,x) memset(v,x,sizeof(v)) #define all(v) v.begin(),v.end() #define ff first #define ss second #define rep(i, a, b) for(int i = a; i < (b); ++i) #define per(i, a, b) for(int i = b-1; i>=a ; i--) #define trav(a, x) for(auto& a : x) #define allin(a , x) for(auto a : x) #define td(v) v.begin(),v.end() #define sz(v) (int)v.size() //#define int long long using namespace std; typedef vector<int> vi; #define y1 abacaba #define left sefude #define right sefudermano typedef long long ll; typedef pair<int,int> pii; inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; } ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));} ll exp(ll a,ll b,ll m){ if(b==0LL) return 1LL; if(b==1LL) return mod(a,m); ll k = mod(exp(a,b/2,m),m); if(b&1LL){ return mod(a*mod(k*k,m),m); } else return mod(k*k,m); } int n,m; const int N = 30100; int b[N],p[N]; const int sq = 175; int vis[N][sq + 15]; int dist[N][sq + 15]; vi aqui[N]; const int inf = 1e9; struct coisa{ int dist,cur,p; coisa(){} coisa(int a,int b,int c){ dist = a; cur = b; p = c; } bool operator<(const coisa& o)const{ return dist > o.dist; } }; #define pwr(x) (x>=sq ? sq + 1 : x) void djkistra(){ for(int i=0;i<N;i++){ for(int j=0;j<sq+10;j++)dist[i][j] = inf; } priority_queue<coisa> pq; dist[b[0]][pwr(p[0])] =0; pq.push(coisa(dist[b[0]][pwr(p[0])],b[0],p[0])); while(!pq.empty()){ coisa c = pq.top(); pq.pop(); if(vis[c.cur][pwr(c.p)])continue; vis[c.cur][pwr(c.p)]=1; int d = dist[c.cur][pwr(c.p)]; int id = c.cur; int cur = c.cur; if(cur < sq){ aqui[id].pb(c.p); } for(int x : aqui[id]){ if(x >= sq){ int t=0; for(int l = cur-x;l>=0;l-=x){ // n * n / sqrt t++; if(dist[l][sq + 1] > d + t){ dist[l][sq + 1] = d + t; pq.push(coisa(dist[l][sq+1],l,x)); } } t=0; for(int l = cur + x;l<n;l+=x){ t++; if(dist[l][sq+1] > d + t){ dist[l][sq + 1] = d + t; pq.push(coisa(dist[l][sq+1],l,x)); } } }else{ // n * sqrt dist[cur][x] = min(dist[cur][x],d); if(cur - x >=0 and dist[cur-x][x] > d + 1){ dist[cur-x][x] = d + 1; pq.push(coisa(dist[cur-x][x],cur - x,x)); } if(cur + x < n and dist[cur + x][x] > d + 1){ dist[cur + x][x] = d + 1; pq.push(coisa(dist[cur + x][x],cur + x,x)); } } } aqui[id].clear(); } int res = inf; for(int i=0;i<sq + 10;i++){ res = min(res,dist[b[1]][i]); } if(res == inf)printf("-1\n"); else printf("%d\n",res); // if(res == inf)cout<<-1<<endl; // else cout << res << endl; } int32_t main(){ // fastio; // cin >> n >> m; scanf("%d %d",&n,&m); for(int i=0;i<m;i++){ //cin >> b[i] >> p[i]; scanf("%d %d",&b[i],&p[i]); aqui[b[i]].pb(p[i]); } djkistra(); // Math -> gcd it all // Did u check N=1? Did you switch N,M? }

Compilation message (stderr)

skyscraper.cpp: In function 'int32_t main()':
skyscraper.cpp:138:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&n,&m);
   ~~~~~^~~~~~~~~~~~~~~
skyscraper.cpp:141:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&b[i],&p[i]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...