oj.uz

Submission #671610

# Submission time Handle Problem Language Result Execution time Memory
671610 2022-12-13T09:52:52 Z MohammadAghil Jakarta Skyscrapers (APIO15_skyscraper) C++17
100 / 100
 254 ms 241940 KB 
      #include <bits/stdc++.h>
//   #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
 using namespace std;
  typedef long long ll;
   typedef pair<int, int> pp;
     #define per(i,r,l) for(int i = (r); i >= (l); i--)
       #define rep(i,l,r) for(int i = (l); i < (r); i++)
          #define all(x) begin(x), end(x)
             #define sz(x) (int)(x).size()
                 #define pb push_back
                     #define ss second
                          #define ff first
                                  void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
void IOS(){
     cin.tie(0) -> sync_with_stdio(0);
     #ifndef ONLINE_JUDGE
          #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
     #else
          #define er(args ...) 0
     #endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 3e4 + 5, sq = 2000, lg = 22, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll,md);return k*k%md*(b&1ll?a:1)%md;}

vector<int> dog[maxn];
map<pp, int> dist;
int dist2[sq][maxn];
bool vis[maxn];

int main(){ IOS();
     int n, m; cin >> n >> m;
     map<pp, vector<int>> is;
     rep(i,0,sq) rep(j,0,n) dist2[i][j] = inf;
     pp bg, en;
     rep(i,0,m){
          int x, p; cin >> x >> p;
          if(!i) bg = {x, p};
          if(i == 1) en = {x, p};
          dog[x].pb(p);
     }
     deque<pp> q;
     q.pb({bg});
     auto set = [&](int x, int p, int w){
          if(p < sq) dist2[p][x] = w;
          else dist[{x, p}] = w;
     };
     auto get = [&](int x, int p){
          if(p < sq) return dist2[p][x];
          return dist.count({x, p})? dist[{x, p}]: int(inf);
     };
     set(bg.ff, bg.ss, 0);
     while(sz(q)){
          auto[x, p] = q.front(); q.pop_front();
          auto add = [&](int x2, int p2, bool bk){ 
               if(x2 > -1 && x2 < n && get(x2, p2) == inf){
                    set(x2, p2, get(x, p) + bk);
                    if(bk) q.pb({x2, p2});
                    else q.push_front({x2, p2});
               }
          };
          if(!vis[x]){
               for(int r: dog[x]){
                    add(x, r, false);
               }
          }
          vis[x] = true;
          add(x+p, p, true), add(x-p, p, true);
     }
     cout << (get(en.ff, en.ss) == inf? -1: get(en.ff, en.ss)) << '\n';
     return 0-0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9428 KB Output is correct
2 Correct 4 ms 9428 KB Output is correct
3 Correct 4 ms 9428 KB Output is correct
4 Correct 5 ms 9428 KB Output is correct
5 Correct 4 ms 9556 KB Output is correct
6 Correct 4 ms 9492 KB Output is correct
7 Correct 4 ms 9556 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Correct 4 ms 9940 KB Output is correct
10 Correct 5 ms 10196 KB Output is correct
11 Correct 5 ms 10196 KB Output is correct
12 Correct 5 ms 10196 KB Output is correct
13 Correct 5 ms 10196 KB Output is correct
14 Correct 5 ms 10196 KB Output is correct
15 Correct 5 ms 10196 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9428 KB Output is correct
2 Correct 4 ms 9428 KB Output is correct
3 Correct 4 ms 9428 KB Output is correct
4 Correct 4 ms 9428 KB Output is correct
5 Correct 4 ms 9556 KB Output is correct
6 Correct 4 ms 9556 KB Output is correct
7 Correct 4 ms 9556 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Correct 5 ms 9864 KB Output is correct
10 Correct 5 ms 10196 KB Output is correct
11 Correct 5 ms 10236 KB Output is correct
12 Correct 5 ms 10196 KB Output is correct
13 Correct 4 ms 10196 KB Output is correct
14 Correct 5 ms 10284 KB Output is correct
15 Correct 5 ms 10196 KB Output is correct
16 Correct 5 ms 10964 KB Output is correct
17 Correct 8 ms 15316 KB Output is correct
18 Correct 10 ms 23124 KB Output is correct
19 Correct 11 ms 25124 KB Output is correct
20 Correct 11 ms 25172 KB Output is correct
21 Correct 6 ms 12508 KB Output is correct
22 Correct 10 ms 23408 KB Output is correct
23 Correct 11 ms 21960 KB Output is correct
24 Correct 12 ms 24276 KB Output is correct
25 Correct 12 ms 25044 KB Output is correct
26 Correct 12 ms 25020 KB Output is correct
27 Correct 12 ms 25044 KB Output is correct
28 Correct 15 ms 25124 KB Output is correct
29 Correct 15 ms 25112 KB Output is correct
30 Correct 12 ms 25044 KB Output is correct
31 Correct 12 ms 25044 KB Output is correct
32 Correct 14 ms 25072 KB Output is correct
33 Correct 15 ms 25044 KB Output is correct
34 Correct 14 ms 25044 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9428 KB Output is correct
2 Correct 4 ms 9428 KB Output is correct
3 Correct 4 ms 9428 KB Output is correct
4 Correct 4 ms 9428 KB Output is correct
5 Correct 4 ms 9556 KB Output is correct
6 Correct 4 ms 9556 KB Output is correct
7 Correct 4 ms 9556 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Correct 4 ms 9940 KB Output is correct
10 Correct 4 ms 10196 KB Output is correct
11 Correct 4 ms 10196 KB Output is correct
12 Correct 4 ms 10196 KB Output is correct
13 Correct 5 ms 10196 KB Output is correct
14 Correct 5 ms 10196 KB Output is correct
15 Correct 4 ms 10196 KB Output is correct
16 Correct 5 ms 10964 KB Output is correct
17 Correct 7 ms 15316 KB Output is correct
18 Correct 10 ms 23124 KB Output is correct
19 Correct 11 ms 25044 KB Output is correct
20 Correct 12 ms 25172 KB Output is correct
21 Correct 5 ms 12536 KB Output is correct
22 Correct 10 ms 23380 KB Output is correct
23 Correct 11 ms 21920 KB Output is correct
24 Correct 12 ms 24276 KB Output is correct
25 Correct 13 ms 25044 KB Output is correct
26 Correct 13 ms 25128 KB Output is correct
27 Correct 12 ms 25044 KB Output is correct
28 Correct 13 ms 25044 KB Output is correct
29 Correct 16 ms 25044 KB Output is correct
30 Correct 13 ms 25072 KB Output is correct
31 Correct 12 ms 25044 KB Output is correct
32 Correct 12 ms 25060 KB Output is correct
33 Correct 15 ms 25044 KB Output is correct
34 Correct 15 ms 25044 KB Output is correct
35 Correct 19 ms 20940 KB Output is correct
36 Correct 10 ms 18060 KB Output is correct
37 Correct 22 ms 25024 KB Output is correct
38 Correct 24 ms 25432 KB Output is correct
39 Correct 25 ms 25496 KB Output is correct
40 Correct 24 ms 25428 KB Output is correct
41 Correct 25 ms 25556 KB Output is correct
42 Correct 15 ms 25280 KB Output is correct
43 Correct 14 ms 25300 KB Output is correct
44 Correct 15 ms 25300 KB Output is correct
45 Correct 25 ms 25552 KB Output is correct
46 Correct 24 ms 25428 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9428 KB Output is correct
2 Correct 4 ms 9428 KB Output is correct
3 Correct 4 ms 9428 KB Output is correct
4 Correct 4 ms 9428 KB Output is correct
5 Correct 4 ms 9556 KB Output is correct
6 Correct 4 ms 9556 KB Output is correct
7 Correct 4 ms 9556 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Correct 5 ms 9940 KB Output is correct
10 Correct 4 ms 10196 KB Output is correct
11 Correct 5 ms 10196 KB Output is correct
12 Correct 6 ms 10324 KB Output is correct
13 Correct 4 ms 10196 KB Output is correct
14 Correct 4 ms 10196 KB Output is correct
15 Correct 5 ms 10196 KB Output is correct
16 Correct 5 ms 11016 KB Output is correct
17 Correct 7 ms 15256 KB Output is correct
18 Correct 10 ms 23124 KB Output is correct
19 Correct 11 ms 25052 KB Output is correct
20 Correct 11 ms 25172 KB Output is correct
21 Correct 6 ms 12480 KB Output is correct
22 Correct 10 ms 23312 KB Output is correct
23 Correct 11 ms 21972 KB Output is correct
24 Correct 12 ms 24276 KB Output is correct
25 Correct 12 ms 25076 KB Output is correct
26 Correct 12 ms 25044 KB Output is correct
27 Correct 12 ms 25044 KB Output is correct
28 Correct 12 ms 25172 KB Output is correct
29 Correct 12 ms 25008 KB Output is correct
30 Correct 12 ms 25044 KB Output is correct
31 Correct 12 ms 25064 KB Output is correct
32 Correct 11 ms 25044 KB Output is correct
33 Correct 14 ms 25044 KB Output is correct
34 Correct 13 ms 25044 KB Output is correct
35 Correct 19 ms 21008 KB Output is correct
36 Correct 10 ms 17948 KB Output is correct
37 Correct 25 ms 25020 KB Output is correct
38 Correct 26 ms 25444 KB Output is correct
39 Correct 24 ms 25484 KB Output is correct
40 Correct 28 ms 25472 KB Output is correct
41 Correct 25 ms 25520 KB Output is correct
42 Correct 14 ms 25300 KB Output is correct
43 Correct 17 ms 25352 KB Output is correct
44 Correct 14 ms 25300 KB Output is correct
45 Correct 33 ms 25428 KB Output is correct
46 Correct 25 ms 25500 KB Output is correct
47 Correct 116 ms 107824 KB Output is correct
48 Correct 83 ms 191272 KB Output is correct
49 Correct 89 ms 208140 KB Output is correct
50 Correct 101 ms 227896 KB Output is correct
51 Correct 196 ms 241748 KB Output is correct
52 Correct 199 ms 241692 KB Output is correct
53 Correct 119 ms 238624 KB Output is correct
54 Correct 105 ms 235916 KB Output is correct
55 Correct 114 ms 235788 KB Output is correct
56 Correct 113 ms 236956 KB Output is correct
57 Correct 116 ms 235980 KB Output is correct
58 Correct 103 ms 236080 KB Output is correct
59 Correct 108 ms 236172 KB Output is correct
60 Correct 107 ms 236076 KB Output is correct
61 Correct 111 ms 236552 KB Output is correct
62 Correct 174 ms 241940 KB Output is correct
63 Correct 198 ms 236528 KB Output is correct
64 Correct 198 ms 236264 KB Output is correct
65 Correct 233 ms 236344 KB Output is correct
66 Correct 254 ms 236492 KB Output is correct
67 Correct 244 ms 236328 KB Output is correct