oj.uz

Submission #244714

# Submission time Handle Problem Language Result Execution time Memory
244714 2020-07-04T16:46:00 Z uacoder123 Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 114 ms 143608 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 short lli;
typedef pair <short,short> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;
vector<pair<short,short>> al[5220000];
int dis[5220000],n;
set<pair<int,short>> s;
map<ii,int> ma;

lli dij(lli so,lli t)
{
  for(int i=0;i<5220000;++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, from, to;
    cin>>n>>m;
    rn=sqrt(n)+1;
    for(lli i=0;i<m;++i)
    {
      lli f,se;
      cin>>f>>se;
      if(i==0) from = f;
      if(i==1) to = f;
      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+from,rn*n+to)<<endl;
  }
  return(0);
}

Compilation message

skyscraper.cpp: In function 'lli dij(lli, lli)':
skyscraper.cpp:33:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(lli i=0;i<al[v.S].size();++i)
                 ~^~~~~~~~~~~~~~~
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:99:29: warning: 'to' may be used uninitialized in this function [-Wmaybe-uninitialized]
     cout<<dij(rn*n+from,rn*n+to)<<endl;
                         ~~~~^~~
skyscraper.cpp:99:19: warning: 'from' may be used uninitialized in this function [-Wmaybe-uninitialized]
     cout<<dij(rn*n+from,rn*n+to)<<endl;
               ~~~~^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 143352 KB Output is correct
2 Correct 99 ms 143336 KB Output is correct
3 Correct 95 ms 143356 KB Output is correct
4 Correct 93 ms 143344 KB Output is correct
5 Correct 94 ms 143408 KB Output is correct
6 Correct 100 ms 143352 KB Output is correct
7 Correct 101 ms 143352 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 143352 KB Output is correct
2 Correct 103 ms 143352 KB Output is correct
3 Correct 94 ms 143228 KB Output is correct
4 Correct 89 ms 143352 KB Output is correct
5 Correct 91 ms 143352 KB Output is correct
6 Correct 93 ms 143352 KB Output is correct
7 Correct 97 ms 143352 KB Output is correct
8 Correct 91 ms 143336 KB Output is correct
9 Correct 96 ms 143480 KB Output is correct
10 Correct 91 ms 143480 KB Output is correct
11 Correct 94 ms 143352 KB Output is correct
12 Correct 106 ms 143352 KB Output is correct
13 Correct 104 ms 143352 KB Output is correct
14 Correct 103 ms 143352 KB Output is correct
15 Correct 109 ms 143480 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 143352 KB Output is correct
2 Correct 92 ms 143352 KB Output is correct
3 Correct 91 ms 143352 KB Output is correct
4 Correct 104 ms 143352 KB Output is correct
5 Correct 102 ms 143352 KB Output is correct
6 Correct 93 ms 143352 KB Output is correct
7 Correct 91 ms 143352 KB Output is correct
8 Correct 95 ms 143352 KB Output is correct
9 Correct 104 ms 143352 KB Output is correct
10 Correct 91 ms 143352 KB Output is correct
11 Correct 93 ms 143352 KB Output is correct
12 Correct 90 ms 143352 KB Output is correct
13 Correct 95 ms 143352 KB Output is correct
14 Correct 102 ms 143480 KB Output is correct
15 Correct 114 ms 143480 KB Output is correct
16 Correct 89 ms 143352 KB Output is correct
17 Correct 93 ms 143608 KB Output is correct
18 Correct 110 ms 143480 KB Output is correct
19 Correct 91 ms 143480 KB Output is correct
20 Incorrect 106 ms 143608 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 143356 KB Output is correct
2 Correct 104 ms 143352 KB Output is correct
3 Correct 93 ms 143352 KB Output is correct
4 Correct 93 ms 143480 KB Output is correct
5 Correct 90 ms 143352 KB Output is correct
6 Correct 96 ms 143352 KB Output is correct
7 Correct 92 ms 143352 KB Output is correct
8 Correct 103 ms 143352 KB Output is correct
9 Correct 90 ms 143356 KB Output is correct
10 Correct 102 ms 143352 KB Output is correct
11 Correct 97 ms 143480 KB Output is correct
12 Correct 99 ms 143480 KB Output is correct
13 Correct 98 ms 143484 KB Output is correct
14 Correct 91 ms 143352 KB Output is correct
15 Correct 91 ms 143352 KB Output is correct
16 Correct 90 ms 143480 KB Output is correct
17 Correct 94 ms 143608 KB Output is correct
18 Correct 95 ms 143404 KB Output is correct
19 Correct 100 ms 143480 KB Output is correct
20 Incorrect 94 ms 143480 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 143352 KB Output is correct
2 Correct 96 ms 143332 KB Output is correct
3 Correct 93 ms 143384 KB Output is correct
4 Correct 104 ms 143352 KB Output is correct
5 Correct 91 ms 143352 KB Output is correct
6 Correct 92 ms 143352 KB Output is correct
7 Correct 100 ms 143352 KB Output is correct
8 Correct 91 ms 143352 KB Output is correct
9 Correct 92 ms 143352 KB Output is correct
10 Correct 96 ms 143480 KB Output is correct
11 Correct 93 ms 143396 KB Output is correct
12 Correct 94 ms 143352 KB Output is correct
13 Correct 101 ms 143352 KB Output is correct
14 Correct 113 ms 143480 KB Output is correct
15 Correct 106 ms 143352 KB Output is correct
16 Correct 90 ms 143480 KB Output is correct
17 Correct 95 ms 143608 KB Output is correct
18 Correct 114 ms 143480 KB Output is correct
19 Correct 93 ms 143480 KB Output is correct
20 Incorrect 93 ms 143480 KB Output isn't correct
21 Halted 0 ms 0 KB -