제출 #610741

#제출 시각아이디문제언어결과실행 시간메모리
610741NicolaAbusaad2014Jakarta Skyscrapers (APIO15_skyscraper)C++14
57 / 100
1010 ms50052 KiB
/** * Prof.Nicola **/ #include <bits/stdc++.h> using namespace std; #define endl "\n" #define mp make_pair #define F first #define S second #define REP(i,l,r) for(long long i=(l);i<(r);i++) #define PER(i,l,r) for(long long i=(r)-1;i>=(l);i--) #define bitl __builtin_clz #define bitr __builtin_ctz #define bits __builtin_popcount const long dx[4]={1,0,-1,0},dz[4]={0,1,0,-1}; const long double pi=3.14159265359; const long long mod=1e9+7; long long p(long long x){while(x&(x-1)){x=x&(x-1);}return x;} long long squared(long long x){return (x*x)%mod;} long long power(long long x,long long p){if(p==0){return 1;}if(p%2==1){return (power(x,p-1)*x)%mod;}return squared(power(x,p/2));} long long inv(long long x){return power(x,mod-2);} long long log(long long x,long long z){if(x<z){return 0;}return 1+log(x/z,z);} template<class T>void re(T&x){cin>>x;} template<class T1,class T2> void re(pair<T1,T2>&x){re(x.first);re(x.second);} template<class T>void re(vector<T>&x){for(long i=0;i<x.size();i++){re(x[i]);}} template<class T>void re(deque<T>&x){for(long i=0;i<x.size();i++){re(x[i]);}} template<class T>void out(T x){cout<<x<<" ";} template<class T1,class T2>void out(pair<T1,T2>x){out(x.first);out(x.second);cout<<endl;} template<class T>void out(vector<T>x,long l=0,long r=0){if(!r){r=x.size();}for(long i=l;i<r;i++){out(x[i]);}cout<<endl;} template<class T>void out(deque<T>x,long l=0,long r=0){if(!r){r=x.size();}for(long i=l;i<r;i++){out(x[i]);}cout<<endl;} template<class T>void out(set<T>x){while(!x.empty()){out(*x.begin());x.erase(*x.begin());}cout<<endl;} template<class T1,class T2>void out(map<T1,T2>x){while(!x.empty()){out(*x.begin());x.erase(x.begin()->first);}cout<<endl;} template<class T>void out(queue<T>x){while(!x.empty()){out(x.front());x.pop();}cout<<endl;} template<class T>void out(priority_queue<T>x){while(!x.empty()){out(x.top());x.pop();}cout<<endl;} template<class T>void out(stack<T>x){while(!x.empty()){out(x.top());x.pop();}cout<<endl;} template<class T>T cross(complex<T>x,complex<T>z){return (conj(x)*z).imag();} template<class T>T dot(complex<T>x,complex<T>z){return (conj(x)*z).real();} set<long long>::iterator T; long long vLE(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>x){return -1;}long long z=p(r-l);while(z){if(l+z<=r&&VT[l+z]<=x){l+=z;}z/=2;}return l;} long long vL(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>=x){return -1;}long long z=p(r-l);while(z){if(l+z<=r&&VT[l+z]<x){l+=z;}z/=2;}return l;} long long vGE(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>=x){return l;}l=vL(x,VT,l,r);if(l==r){return -1;}return l+1;} long long vG(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>x){return l;}l=vLE(x,VT,l,r);if(l==r){return -1;}return l+1;} long long sLE(long long x,set<long long>&ST){if(ST.count(x)){return x;}if(*ST.begin()>x){return -1;}ST.insert(x);T=ST.find(x);T--;ST.erase(x);return *T;} long long sL(long long x,set<long long>&ST){if(*ST.begin()>=x){return -1;}if(ST.count(x)){T=ST.find(x);T--;return *T;}ST.insert(x);T=ST.find(x);T--;ST.erase(x);return *T;} long long sGE(long long x,set<long long>&ST){if(ST.count(x)){return x;}if(*ST.rbegin()<x){return -1;}ST.insert(x);T=ST.find(x);T++;ST.erase(x);return *T;} long long sG(long long x,set<long long>&ST){if(*ST.rbegin()<=x){return -1;}if(ST.count(x)){T=ST.find(x);T++;return *T;}ST.insert(x);T=ST.find(x);T++;ST.erase(x);return *T;} int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); long n,m,s,cost,pos,jump,ans,inf=1e9; cin>>n>>m; s=sqrt(n)+1; vector<pair<long,long> >v(m); vector<bool>ok(n); re(v); vector<vector<long> >possible(n); vector<map<long,bool> >vis(n); vector<long>path(n,inf); REP(i,0,m){ if(i==1){ continue; } possible[v[i].F].push_back(v[i].S); } priority_queue<pair<long,pair<long,long> > >pq; pq.push(mp(0,mp(v[0].F,v[0].S))); while(!pq.empty()){ cost=pq.top().F; pos=pq.top().S.F; jump=pq.top().S.S; pq.pop(); if(vis[pos][jump]){ continue; } path[pos]=min(path[pos],-cost); vis[pos][jump]=true; if(ok[pos]){ if(pos+jump<n){ pq.push(mp(cost-1,mp(pos+jump,jump))); } if(pos-jump>=0){ pq.push(mp(cost-1,mp(pos-jump,jump))); } continue; } if(pos+jump<n){ pq.push(mp(cost-1,mp(pos+jump,jump))); } if(pos-jump>=0){ pq.push(mp(cost-1,mp(pos-jump,jump))); } ok[pos]=true; REP(i,0,possible[pos].size()){ pq.push(mp(cost,mp(pos,possible[pos][i]))); } } ans=path[v[1].F]; if(ans==inf){ cout<<-1<<endl; return 0; } cout<<ans<<endl; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:11:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
      |                                         ^
skyscraper.cpp:95:9: note: in expansion of macro 'REP'
   95 |         REP(i,0,possible[pos].size()){
      |         ^~~
skyscraper.cpp:52:14: warning: variable 's' set but not used [-Wunused-but-set-variable]
   52 |     long n,m,s,cost,pos,jump,ans,inf=1e9;
      |              ^
skyscraper.cpp: In instantiation of 'void re(std::vector<_Tp>&) [with T = std::pair<long int, long int>]':
skyscraper.cpp:57:9:   required from here
skyscraper.cpp:26:53: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 | template<class T>void re(vector<T>&x){for(long i=0;i<x.size();i++){re(x[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...