oj.uz

Submission #244699

# Submission time Handle Problem Language Result Execution time Memory
244699 2020-07-04T16:01:12 Z uacoder123 Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 882 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
 
typedef int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;
vector<ii> al[5430000];
lli dis[5430000],n;
set<ii> s;
lli dij(lli so,lli t)
{
  for(lli i=0;i<5430000;++i)
    dis[i]=1000000000;
  s.insert(mp(0,so));
  dis[so]=0;
  while(s.size()!=0)
  {
    ii v=(*s.begin());
    s.erase(s.begin());
    dis[v.S]=v.F;
    for(lli i=0;i<al[v.S].size();++i)
    {
      if(al[v.S][i].S+v.F<dis[al[v.S][i].F])
      {
       s.erase(mp(dis[al[v.S][i].F],al[v.S][i].F));
       dis[al[v.S][i].F]=al[v.S][i].S+v.F;
       s.insert(mp(dis[al[v.S][i].F],al[v.S][i].F)); 
      }
    }
  }
  if(dis[t]==1000000000)
    return(-1);
  return(dis[t]);
}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  lli test=1;
  for(;test>0;--test)
  {
    lli m,rn;
    cin>>n>>m;
    rn=sqrt(n)+1;
    ii dg[m];
    map<ii,int> ma;
    for(lli i=0;i<m;++i)
    {
      lli f,se;
      cin>>f>>se;
      dg[i]=mp(f,se);
      if(se<rn)
      {
        al[rn*n+f].pb(mp((se)*n+f,0));
        al[se*n+f].pb(mp(rn*n+f,0));
        if(se==0||ma.find(mp(f%se,se))!=ma.end())
          continue;
        ma[mp(f%se,se)]=1;
        for(lli j=f%se;j<n;j+=se)
        {
          if(j+se<n)
          {
            al[se*n+j].pb(mp(se*n+j+se,1));
            al[se*n+j+se].pb(mp(se*n+j,1));
          }
          if(j+se<n)
            al[se*n+j].pb(mp(rn*n+j+se,1));
          if(j-se>=0)
            al[se*n+j].pb(mp(rn*n+j-  se,1));
        }
      }
      if(se>=rn)
      {
        lli p=f+se;
        while(p<n)
        {
          al[rn*n+f].pb(mp(rn*n+p,(p-f)/se));
          p+=se;
        }
        p=f-se;
        while(p>=0)
        {
          al[rn*n+f].pb(mp(rn*n+p,(f-p)/se));
          p-=se;
        }
      }
    }
    cout<<dij(rn*n+dg[0].F,rn*n+dg[1].F)<<endl;
  }
  return(0);
}

Compilation message

skyscraper.cpp: In function 'lli dij(lli, lli)':
skyscraper.cpp:31:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(lli i=0;i<al[v.S].size();++i)
                 ~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 149112 KB Output is correct
2 Correct 91 ms 149112 KB Output is correct
3 Correct 96 ms 149112 KB Output is correct
4 Correct 93 ms 149112 KB Output is correct
5 Correct 93 ms 149112 KB Output is correct
6 Correct 94 ms 149112 KB Output is correct
7 Correct 115 ms 149112 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 149112 KB Output is correct
2 Correct 95 ms 149112 KB Output is correct
3 Correct 92 ms 149112 KB Output is correct
4 Correct 109 ms 149112 KB Output is correct
5 Correct 96 ms 149112 KB Output is correct
6 Correct 92 ms 149112 KB Output is correct
7 Correct 104 ms 149112 KB Output is correct
8 Correct 101 ms 149112 KB Output is correct
9 Correct 95 ms 149112 KB Output is correct
10 Correct 93 ms 149108 KB Output is correct
11 Correct 101 ms 149240 KB Output is correct
12 Correct 90 ms 149112 KB Output is correct
13 Correct 109 ms 149240 KB Output is correct
14 Correct 111 ms 149240 KB Output is correct
15 Correct 102 ms 149240 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 149112 KB Output is correct
2 Correct 92 ms 149152 KB Output is correct
3 Correct 95 ms 149112 KB Output is correct
4 Correct 105 ms 149116 KB Output is correct
5 Correct 90 ms 149112 KB Output is correct
6 Correct 94 ms 149116 KB Output is correct
7 Correct 91 ms 149112 KB Output is correct
8 Correct 102 ms 149240 KB Output is correct
9 Correct 91 ms 149112 KB Output is correct
10 Correct 92 ms 149112 KB Output is correct
11 Correct 103 ms 149244 KB Output is correct
12 Correct 94 ms 149112 KB Output is correct
13 Correct 102 ms 149240 KB Output is correct
14 Correct 92 ms 149368 KB Output is correct
15 Correct 97 ms 149240 KB Output is correct
16 Correct 112 ms 149244 KB Output is correct
17 Correct 105 ms 149496 KB Output is correct
18 Correct 95 ms 149272 KB Output is correct
19 Correct 92 ms 149240 KB Output is correct
20 Correct 97 ms 149368 KB Output is correct
21 Correct 111 ms 149112 KB Output is correct
22 Correct 92 ms 149240 KB Output is correct
23 Correct 104 ms 149368 KB Output is correct
24 Correct 101 ms 149496 KB Output is correct
25 Correct 96 ms 149368 KB Output is correct
26 Correct 99 ms 149496 KB Output is correct
27 Correct 94 ms 149496 KB Output is correct
28 Correct 99 ms 149880 KB Output is correct
29 Correct 112 ms 152184 KB Output is correct
30 Correct 99 ms 149880 KB Output is correct
31 Correct 105 ms 150624 KB Output is correct
32 Correct 97 ms 149880 KB Output is correct
33 Correct 126 ms 153592 KB Output is correct
34 Correct 137 ms 153592 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 149112 KB Output is correct
2 Correct 117 ms 149112 KB Output is correct
3 Correct 98 ms 149112 KB Output is correct
4 Correct 102 ms 149112 KB Output is correct
5 Correct 105 ms 149112 KB Output is correct
6 Correct 93 ms 149112 KB Output is correct
7 Correct 102 ms 149112 KB Output is correct
8 Correct 97 ms 149112 KB Output is correct
9 Correct 105 ms 149052 KB Output is correct
10 Correct 100 ms 149112 KB Output is correct
11 Correct 104 ms 149272 KB Output is correct
12 Correct 107 ms 149112 KB Output is correct
13 Correct 92 ms 149240 KB Output is correct
14 Correct 96 ms 149240 KB Output is correct
15 Correct 95 ms 149240 KB Output is correct
16 Correct 93 ms 149240 KB Output is correct
17 Correct 108 ms 149500 KB Output is correct
18 Correct 91 ms 149248 KB Output is correct
19 Correct 91 ms 149240 KB Output is correct
20 Correct 93 ms 149368 KB Output is correct
21 Correct 93 ms 149112 KB Output is correct
22 Correct 93 ms 149240 KB Output is correct
23 Correct 94 ms 149352 KB Output is correct
24 Correct 100 ms 149496 KB Output is correct
25 Correct 94 ms 149368 KB Output is correct
26 Correct 96 ms 149496 KB Output is correct
27 Correct 94 ms 149368 KB Output is correct
28 Correct 106 ms 149880 KB Output is correct
29 Correct 130 ms 152056 KB Output is correct
30 Correct 100 ms 149880 KB Output is correct
31 Correct 117 ms 150648 KB Output is correct
32 Correct 103 ms 149880 KB Output is correct
33 Correct 124 ms 153592 KB Output is correct
34 Correct 124 ms 153592 KB Output is correct
35 Correct 111 ms 151544 KB Output is correct
36 Correct 97 ms 149624 KB Output is correct
37 Correct 125 ms 153336 KB Output is correct
38 Correct 141 ms 153080 KB Output is correct
39 Correct 145 ms 153080 KB Output is correct
40 Correct 124 ms 153116 KB Output is correct
41 Correct 124 ms 153080 KB Output is correct
42 Correct 116 ms 150456 KB Output is correct
43 Correct 103 ms 150516 KB Output is correct
44 Correct 98 ms 150324 KB Output is correct
45 Correct 140 ms 157048 KB Output is correct
46 Correct 135 ms 157176 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 149112 KB Output is correct
2 Correct 96 ms 149112 KB Output is correct
3 Correct 100 ms 149112 KB Output is correct
4 Correct 98 ms 149112 KB Output is correct
5 Correct 100 ms 149052 KB Output is correct
6 Correct 96 ms 149112 KB Output is correct
7 Correct 97 ms 149112 KB Output is correct
8 Correct 94 ms 149124 KB Output is correct
9 Correct 92 ms 149112 KB Output is correct
10 Correct 99 ms 149240 KB Output is correct
11 Correct 95 ms 149160 KB Output is correct
12 Correct 98 ms 149240 KB Output is correct
13 Correct 91 ms 149240 KB Output is correct
14 Correct 92 ms 149240 KB Output is correct
15 Correct 94 ms 149240 KB Output is correct
16 Correct 93 ms 149240 KB Output is correct
17 Correct 107 ms 149624 KB Output is correct
18 Correct 104 ms 149368 KB Output is correct
19 Correct 104 ms 149240 KB Output is correct
20 Correct 95 ms 149368 KB Output is correct
21 Correct 96 ms 149240 KB Output is correct
22 Correct 96 ms 149332 KB Output is correct
23 Correct 96 ms 149368 KB Output is correct
24 Correct 96 ms 149496 KB Output is correct
25 Correct 96 ms 149368 KB Output is correct
26 Correct 96 ms 149496 KB Output is correct
27 Correct 94 ms 149496 KB Output is correct
28 Correct 96 ms 149880 KB Output is correct
29 Correct 115 ms 152144 KB Output is correct
30 Correct 98 ms 149880 KB Output is correct
31 Correct 105 ms 150776 KB Output is correct
32 Correct 114 ms 149880 KB Output is correct
33 Correct 127 ms 153592 KB Output is correct
34 Correct 123 ms 153592 KB Output is correct
35 Correct 113 ms 151672 KB Output is correct
36 Correct 97 ms 149624 KB Output is correct
37 Correct 136 ms 153336 KB Output is correct
38 Correct 136 ms 153080 KB Output is correct
39 Correct 127 ms 153056 KB Output is correct
40 Correct 127 ms 153080 KB Output is correct
41 Correct 125 ms 152956 KB Output is correct
42 Correct 99 ms 150436 KB Output is correct
43 Correct 98 ms 150468 KB Output is correct
44 Correct 112 ms 150368 KB Output is correct
45 Correct 145 ms 157048 KB Output is correct
46 Correct 141 ms 157304 KB Output is correct
47 Correct 315 ms 171000 KB Output is correct
48 Correct 122 ms 156408 KB Output is correct
49 Correct 109 ms 152824 KB Output is correct
50 Correct 110 ms 153464 KB Output is correct
51 Correct 209 ms 159608 KB Output is correct
52 Correct 212 ms 160760 KB Output is correct
53 Correct 126 ms 152440 KB Output is correct
54 Correct 109 ms 150520 KB Output is correct
55 Correct 104 ms 151800 KB Output is correct
56 Correct 117 ms 153336 KB Output is correct
57 Correct 324 ms 169720 KB Output is correct
58 Correct 129 ms 153476 KB Output is correct
59 Correct 126 ms 154740 KB Output is correct
60 Correct 153 ms 155764 KB Output is correct
61 Correct 125 ms 154520 KB Output is correct
62 Correct 184 ms 164768 KB Output is correct
63 Correct 189 ms 174328 KB Output is correct
64 Correct 212 ms 182648 KB Output is correct
65 Correct 882 ms 231288 KB Output is correct
66 Runtime error 624 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
67 Halted 0 ms 0 KB -