oj.uz

Submission #228468

# Submission time Handle Problem Language Result Execution time Memory
228468 2020-05-01T05:26:52 Z caoash Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 1000 ms 132436 KB 
#pragma GCC optimize("Ofast")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef pair<int, pi> pii;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
#define fax(i, a) for (int i = 0; i < (a); i++)
#define f0x(i, a, b) for (int i = (a); i < (b); i++)
#define f0xd(i,a,b) for (int i = (b)-1; i >= (a); i--)
#define faxd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto& a : x)
#define memeset memset
 
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
 
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rsz resize
 
template<class T> void ckmin(T &a, T b) { a = min(a, b); }
template<class T> void ckmax(T &a, T b) { a = max(a, b); }
 
namespace input {
    template<class T> void re(complex<T>& x);
    template<class T1, class T2> void re(pair<T1,T2>& p);
    template<class T> void re(vector<T>& a);
    template<class T, size_t SZ> void re(array<T,SZ>& a);
 
    template<class T> void re(T& x) { cin >> x; }
    void re(double& x) { string t; re(t); x = stod(t); }
    void re(ld& x) { string t; re(t); x = stold(t); }
    template<class T, class... Ts> void re(T& t, Ts&... ts) { 
        re(t); re(ts...); 
    }
 
    template<class T> void re(complex<T>& x) { T a,b; re(a,b); x = cd(a,b); }
    template<class T1, class T2> void re(pair<T1,T2>& p) { re(p.f,p.s); }
    template<class T> void re(vector<T>& a) { fax(i,sz(a)) re(a[i]); }
    template<class T, size_t SZ> void re(array<T,SZ>& a) { fax(i,SZ) re(a[i]); }
}
 
using namespace input;
 
namespace output {
    void pr(int x) { cout << x; }
    void pr(long x) { cout << x; }
    void pr(ll x) { cout << x; }
    void pr(unsigned x) { cout << x; }
    void pr(unsigned long x) { cout << x; }
    void pr(unsigned long long x) { cout << x; }
    void pr(float x) { cout << x; }
    void pr(double x) { cout << x; }
    void pr(ld x) { cout << x; }
    void pr(char x) { cout << x; }
    void pr(const char* x) { cout << x; }
    void pr(const string& x) { cout << x; }
    void pr(bool x) { pr(x ? "true" : "false"); }
    
    template<class T1, class T2> void pr(const pair<T1,T2>& x);
    template<class T> void pr(const T& x);
    
    template<class T, class... Ts> void pr(const T& t, const Ts&... ts) { 
        pr(t); pr(ts...); 
    }
    template<class T1, class T2> void pr(const pair<T1,T2>& x) { 
        pr("{",x.f,", ",x.s,"}"); 
    }
    template<class T> void pr(const T& x) { 
        pr("{"); // const iterator needed for vector<bool>
        bool fst = 1; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0; 
        pr("}");
    }
    
    void ps() { pr("\n"); } // print w/ spaces
    template<class T, class... Ts> void ps(const T& t, const Ts&... ts) { 
        pr(t); if (sizeof...(ts)) pr(" "); ps(ts...); 
    }
    
    void pc() { pr("]\n"); } // debug w/ commas
    template<class T, class... Ts> void pc(const T& t, const Ts&... ts) { 
        pr(t); if (sizeof...(ts)) pr(", "); pc(ts...); 
    }
    #define dbg(x...) pr("[",#x,"] = ["), pc(x);
}
 
using namespace output;
 
namespace io {
    void setIn(string s) { freopen(s.c_str(),"r",stdin); }
    void setOut(string s) { freopen(s.c_str(),"w",stdout); }
    void setIO(string s = "") {
        ios_base::sync_with_stdio(0); cin.tie(0); // fast I/O
        if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
    }
}
 
using namespace io;
 
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
 
const int MOD = 1000000007; // 998244353
const ll INF = 1e18;
const int MX = 30005;
const ld PI = 4*atan((ld)1);
 
struct pair_hash
{
	template <class T1, class T2>
	std::size_t operator () (std::pair<T1, T2> const &pair) const
	{
		std::size_t h1 = std::hash<T1>()(pair.first);
		std::size_t h2 = std::hash<T2>()(pair.second);
 
		return h1 ^ h2;
	}
};

map<pi, vector<pii>> adj; vector<pi> low, high; unordered_set<int> vals; unordered_set<pi, pair_hash> vis; cc_hash_table<pi,ll, pair_hash> dist;
 
int main() {
   setIO(); 
   int N,M; re(N,M);   
   const int LIM = ceil(sqrt((double)N));
   pi fst = {-1,-1}; pi sec = {-1,-1};
   fax(i,M){
      int b,p; re(b,p);  
      if(fst.f == -1){
         fst = mp(b,p);
      } 
      else if(sec.f == -1){
         sec = mp(b,p);
      }
      if(p <= LIM){
         low.pb(mp(b,p));
         vals.insert(p);
      }
      else{
         high.pb(mp(b,p));
      }
   }
   trav(curr, low){
      adj[mp(curr.f, -1)].pb(mp(0,mp(curr.f, curr.s)));
      //dbg(mp(curr.f, -1), mp(0,mp(curr.f,curr.s)));
   }
   trav(curr, high){
      for(int j = 1; curr.f + (curr.s*j) < N; j++){
          adj[mp(curr.f,-1)].pb(mp(j,mp(curr.f+(curr.s*j),-1)));
          //dbg(mp(i,curr.s),mp(j,mp(i+(curr.s*j),-1)));
       }
       for(int j = 1; curr.f - (curr.s*j) >= 0; j++){
          adj[mp(curr.f,-1)].pb(mp(j,mp(curr.f-(curr.s*j),-1)));
          //dbg(mp(i,curr.s),mp(j,mp(i-(curr.s*j),-1)));
       }
   }
   fax(i,N){
     dist[mp(i,-1)] = INF;
     trav(curr, vals){
      adj[mp(i,curr)].pb(mp(0,mp(i,-1)));  
      dist[mp(i,curr)] = INF;
      if(i-curr >= 0){
         adj[mp(i, curr)].pb(mp(1,mp(i-curr,curr)));
      }
      if(i + curr < N){
         adj[mp(i,curr)].pb(mp(1,mp(i+curr,curr)));
      }
     }
   }
   priority_queue<pair<ll,pi>> pq;
   pq.push(mp(0,mp(fst.f, -1)));
   dist[mp(fst.f, -1)] = 0;
   while(!pq.empty()){
      pair<ll,pi> fr = pq.top(); pq.pop();
      if(vis.count(fr.s)){
         continue;
      }
      for(pii to : adj[fr.s]){
         if(vis.count(to.s)){
            continue;
         }
         if(dist[to.s] > dist[fr.s] + to.f){
            dist[to.s] = dist[fr.s] + to.f;
            pq.push(mp(-dist[to.s], to.s));
         }
      }
      vis.insert(fr.s);
   }
   ll d = dist[mp(sec.f, -1)];
   if(d != INF){
      pr(d, "\n");
      return 0;
   }
   pr(-1, "\n");
}

Compilation message

skyscraper.cpp: In function 'void io::setIn(std::__cxx11::string)':
skyscraper.cpp:112:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     void setIn(string s) { freopen(s.c_str(),"r",stdin); }
                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp: In function 'void io::setOut(std::__cxx11::string)':
skyscraper.cpp:113:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     void setOut(string s) { freopen(s.c_str(),"w",stdout); }
                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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 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 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 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 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 432 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 6 ms 640 KB Output is correct
11 Correct 7 ms 640 KB Output is correct
12 Correct 5 ms 512 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 6 ms 640 KB Output is correct
15 Correct 6 ms 768 KB Output is correct

Subtask #3
14.0 / 14.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 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 6 ms 640 KB Output is correct
11 Correct 6 ms 640 KB Output is correct
12 Correct 5 ms 512 KB Output is correct
13 Correct 5 ms 512 KB Output is correct
14 Correct 6 ms 640 KB Output is correct
15 Correct 6 ms 768 KB Output is correct
16 Correct 7 ms 1024 KB Output is correct
17 Correct 32 ms 5104 KB Output is correct
18 Correct 36 ms 7796 KB Output is correct
19 Correct 19 ms 4728 KB Output is correct
20 Correct 8 ms 1280 KB Output is correct
21 Correct 7 ms 1024 KB Output is correct
22 Correct 21 ms 4984 KB Output is correct
23 Correct 34 ms 6512 KB Output is correct
24 Correct 68 ms 12016 KB Output is correct
25 Correct 13 ms 2048 KB Output is correct
26 Correct 59 ms 10732 KB Output is correct
27 Correct 33 ms 6904 KB Output is correct
28 Correct 95 ms 13552 KB Output is correct
29 Correct 205 ms 17508 KB Output is correct
30 Correct 31 ms 5264 KB Output is correct
31 Correct 74 ms 9576 KB Output is correct
32 Correct 23 ms 4220 KB Output is correct
33 Correct 402 ms 23340 KB Output is correct
34 Correct 363 ms 23396 KB Output is correct

Subtask #4
21.0 / 21.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 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 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 6 ms 640 KB Output is correct
11 Correct 6 ms 640 KB Output is correct
12 Correct 6 ms 640 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 6 ms 640 KB Output is correct
15 Correct 6 ms 768 KB Output is correct
16 Correct 7 ms 1024 KB Output is correct
17 Correct 31 ms 5104 KB Output is correct
18 Correct 35 ms 7788 KB Output is correct
19 Correct 19 ms 4728 KB Output is correct
20 Correct 8 ms 1280 KB Output is correct
21 Correct 7 ms 1024 KB Output is correct
22 Correct 21 ms 4856 KB Output is correct
23 Correct 34 ms 6512 KB Output is correct
24 Correct 74 ms 11964 KB Output is correct
25 Correct 12 ms 2048 KB Output is correct
26 Correct 52 ms 10860 KB Output is correct
27 Correct 32 ms 6896 KB Output is correct
28 Correct 84 ms 13544 KB Output is correct
29 Correct 190 ms 17508 KB Output is correct
30 Correct 28 ms 5232 KB Output is correct
31 Correct 66 ms 9424 KB Output is correct
32 Correct 22 ms 4220 KB Output is correct
33 Correct 370 ms 23268 KB Output is correct
34 Correct 412 ms 23396 KB Output is correct
35 Correct 152 ms 13920 KB Output is correct
36 Correct 51 ms 8172 KB Output is correct
37 Correct 363 ms 23780 KB Output is correct
38 Correct 363 ms 22912 KB Output is correct
39 Correct 357 ms 22896 KB Output is correct
40 Correct 312 ms 23024 KB Output is correct
41 Correct 314 ms 22896 KB Output is correct
42 Correct 67 ms 11376 KB Output is correct
43 Correct 43 ms 7540 KB Output is correct
44 Correct 14 ms 1852 KB Output is correct
45 Correct 372 ms 28412 KB Output is correct
46 Correct 417 ms 28408 KB Output is correct

Subtask #5
0 / 43.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 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 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 6 ms 640 KB Output is correct
11 Correct 6 ms 768 KB Output is correct
12 Correct 6 ms 512 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 6 ms 640 KB Output is correct
15 Correct 6 ms 640 KB Output is correct
16 Correct 7 ms 1024 KB Output is correct
17 Correct 30 ms 5104 KB Output is correct
18 Correct 32 ms 7796 KB Output is correct
19 Correct 19 ms 4728 KB Output is correct
20 Correct 8 ms 1280 KB Output is correct
21 Correct 7 ms 1024 KB Output is correct
22 Correct 21 ms 4984 KB Output is correct
23 Correct 30 ms 6520 KB Output is correct
24 Correct 68 ms 12016 KB Output is correct
25 Correct 11 ms 2048 KB Output is correct
26 Correct 53 ms 10732 KB Output is correct
27 Correct 33 ms 6896 KB Output is correct
28 Correct 86 ms 13552 KB Output is correct
29 Correct 174 ms 17508 KB Output is correct
30 Correct 28 ms 5240 KB Output is correct
31 Correct 68 ms 9452 KB Output is correct
32 Correct 23 ms 4220 KB Output is correct
33 Correct 366 ms 23272 KB Output is correct
34 Correct 428 ms 23360 KB Output is correct
35 Correct 148 ms 13944 KB Output is correct
36 Correct 47 ms 8172 KB Output is correct
37 Correct 402 ms 23672 KB Output is correct
38 Correct 353 ms 22900 KB Output is correct
39 Correct 327 ms 22880 KB Output is correct
40 Correct 339 ms 22900 KB Output is correct
41 Correct 321 ms 22896 KB Output is correct
42 Correct 64 ms 11380 KB Output is correct
43 Correct 36 ms 7540 KB Output is correct
44 Correct 13 ms 1852 KB Output is correct
45 Correct 426 ms 28220 KB Output is correct
46 Correct 422 ms 28408 KB Output is correct
47 Execution timed out 1102 ms 132436 KB Time limit exceeded
48 Halted 0 ms 0 KB -