oj.uz

답안 #244647

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
244647 2020-07-04T13:32:01 Z uacoder123 Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 521 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[6*1000000];
lli dis[6000000];
set<ii> s;
lli dij(lli so,lli t)
{
  for(lli i=0;i<6000000;++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 n,m,rn;
    cin>>n>>m;
    rn=sqrt(n)+1;
    ii dg[m];
    for(lli i=1;i<rn;++i)
    {
      for(lli j=0;j<n;++j)
      {
        if(j+i<n)
        {
          al[i*n+j].pb(mp(i*n+j+i,1));
          al[i*n+j+i].pb(mp(i*n+j,1));
        }
        if(j+i<n)
          al[i*n+j].pb(mp(rn*n+j+i,1));
        if(j-i>=0)
          al[i*n+j].pb(mp(rn*n+j-i,1));
      }
    }
    for(lli i=0;i<m;++i)
    {
      lli f,se;
      cin>>f>>se;
      dg[i]=mp(f,se);
      al[rn*n+f].pb(mp((se)*n+f,0));
      al[se*n+f].pb(mp(rn*n+f,0));
      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(dg[0].S*n+dg[0].F,dg[1].S*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

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 164728 KB Output is correct
2 Correct 95 ms 164728 KB Output is correct
3 Correct 97 ms 164728 KB Output is correct
4 Correct 104 ms 164728 KB Output is correct
5 Correct 95 ms 164728 KB Output is correct
6 Correct 105 ms 164704 KB Output is correct
7 Correct 99 ms 164728 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 164728 KB Output is correct
2 Correct 98 ms 164728 KB Output is correct
3 Correct 95 ms 164728 KB Output is correct
4 Correct 93 ms 164728 KB Output is correct
5 Correct 95 ms 164728 KB Output is correct
6 Correct 93 ms 164728 KB Output is correct
7 Correct 94 ms 164728 KB Output is correct
8 Correct 96 ms 164728 KB Output is correct
9 Correct 102 ms 164728 KB Output is correct
10 Correct 96 ms 164728 KB Output is correct
11 Correct 98 ms 164984 KB Output is correct
12 Correct 104 ms 164856 KB Output is correct
13 Correct 104 ms 164856 KB Output is correct
14 Correct 104 ms 164984 KB Output is correct
15 Correct 107 ms 164984 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 164728 KB Output is correct
2 Correct 106 ms 164728 KB Output is correct
3 Correct 100 ms 164728 KB Output is correct
4 Correct 104 ms 164728 KB Output is correct
5 Correct 98 ms 164728 KB Output is correct
6 Correct 94 ms 164728 KB Output is correct
7 Correct 96 ms 164728 KB Output is correct
8 Correct 95 ms 164728 KB Output is correct
9 Correct 107 ms 164728 KB Output is correct
10 Correct 101 ms 164728 KB Output is correct
11 Correct 97 ms 164984 KB Output is correct
12 Correct 96 ms 164856 KB Output is correct
13 Correct 98 ms 164856 KB Output is correct
14 Correct 95 ms 164936 KB Output is correct
15 Correct 97 ms 164984 KB Output is correct
16 Correct 98 ms 164984 KB Output is correct
17 Correct 101 ms 165872 KB Output is correct
18 Correct 106 ms 168184 KB Output is correct
19 Correct 110 ms 168952 KB Output is correct
20 Correct 110 ms 168952 KB Output is correct
21 Correct 105 ms 165112 KB Output is correct
22 Correct 106 ms 168264 KB Output is correct
23 Correct 110 ms 167800 KB Output is correct
24 Correct 118 ms 168824 KB Output is correct
25 Correct 124 ms 168956 KB Output is correct
26 Correct 120 ms 168952 KB Output is correct
27 Correct 111 ms 168920 KB Output is correct
28 Correct 113 ms 169080 KB Output is correct
29 Correct 117 ms 168952 KB Output is correct
30 Correct 116 ms 168824 KB Output is correct
31 Correct 114 ms 168952 KB Output is correct
32 Correct 127 ms 169080 KB Output is correct
33 Correct 124 ms 169464 KB Output is correct
34 Correct 133 ms 169464 KB Output is correct

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 95 ms 164728 KB Output is correct
2 Correct 97 ms 164728 KB Output is correct
3 Correct 96 ms 164732 KB Output is correct
4 Correct 99 ms 164728 KB Output is correct
5 Correct 101 ms 164728 KB Output is correct
6 Correct 103 ms 164728 KB Output is correct
7 Correct 95 ms 164728 KB Output is correct
8 Correct 94 ms 164728 KB Output is correct
9 Correct 94 ms 164728 KB Output is correct
10 Correct 99 ms 164828 KB Output is correct
11 Correct 98 ms 164984 KB Output is correct
12 Correct 94 ms 164856 KB Output is correct
13 Correct 96 ms 164856 KB Output is correct
14 Correct 96 ms 165112 KB Output is correct
15 Correct 97 ms 164984 KB Output is correct
16 Correct 103 ms 164856 KB Output is correct
17 Correct 105 ms 165864 KB Output is correct
18 Correct 106 ms 168188 KB Output is correct
19 Correct 109 ms 168952 KB Output is correct
20 Correct 108 ms 168952 KB Output is correct
21 Correct 95 ms 165112 KB Output is correct
22 Correct 110 ms 168292 KB Output is correct
23 Correct 110 ms 167676 KB Output is correct
24 Correct 114 ms 168784 KB Output is correct
25 Correct 109 ms 168984 KB Output is correct
26 Correct 110 ms 168952 KB Output is correct
27 Correct 112 ms 168952 KB Output is correct
28 Correct 111 ms 169080 KB Output is correct
29 Correct 126 ms 168952 KB Output is correct
30 Correct 116 ms 168824 KB Output is correct
31 Correct 113 ms 168952 KB Output is correct
32 Correct 114 ms 169084 KB Output is correct
33 Correct 129 ms 169592 KB Output is correct
34 Correct 121 ms 169464 KB Output is correct
35 Correct 141 ms 170232 KB Output is correct
36 Correct 107 ms 166776 KB Output is correct
37 Correct 152 ms 171780 KB Output is correct
38 Correct 154 ms 172792 KB Output is correct
39 Correct 172 ms 172664 KB Output is correct
40 Correct 176 ms 172792 KB Output is correct
41 Correct 158 ms 172792 KB Output is correct
42 Correct 117 ms 169972 KB Output is correct
43 Correct 118 ms 169972 KB Output is correct
44 Correct 115 ms 169908 KB Output is correct
45 Correct 149 ms 175612 KB Output is correct
46 Correct 148 ms 175608 KB Output is correct

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 164728 KB Output is correct
2 Correct 102 ms 164728 KB Output is correct
3 Correct 104 ms 164728 KB Output is correct
4 Correct 96 ms 164804 KB Output is correct
5 Correct 98 ms 164728 KB Output is correct
6 Correct 94 ms 164728 KB Output is correct
7 Correct 93 ms 164728 KB Output is correct
8 Correct 93 ms 164728 KB Output is correct
9 Correct 96 ms 164728 KB Output is correct
10 Correct 95 ms 164728 KB Output is correct
11 Correct 97 ms 164984 KB Output is correct
12 Correct 94 ms 164856 KB Output is correct
13 Correct 98 ms 164856 KB Output is correct
14 Correct 95 ms 164984 KB Output is correct
15 Correct 104 ms 164988 KB Output is correct
16 Correct 101 ms 164868 KB Output is correct
17 Correct 104 ms 165880 KB Output is correct
18 Correct 111 ms 168184 KB Output is correct
19 Correct 108 ms 168824 KB Output is correct
20 Correct 111 ms 169080 KB Output is correct
21 Correct 98 ms 165112 KB Output is correct
22 Correct 107 ms 168312 KB Output is correct
23 Correct 105 ms 167672 KB Output is correct
24 Correct 112 ms 168696 KB Output is correct
25 Correct 115 ms 168952 KB Output is correct
26 Correct 111 ms 168952 KB Output is correct
27 Correct 110 ms 168952 KB Output is correct
28 Correct 110 ms 169080 KB Output is correct
29 Correct 122 ms 168952 KB Output is correct
30 Correct 111 ms 168828 KB Output is correct
31 Correct 116 ms 168952 KB Output is correct
32 Correct 109 ms 169084 KB Output is correct
33 Correct 127 ms 169464 KB Output is correct
34 Correct 122 ms 169464 KB Output is correct
35 Correct 139 ms 170104 KB Output is correct
36 Correct 106 ms 166776 KB Output is correct
37 Correct 151 ms 171768 KB Output is correct
38 Correct 177 ms 172792 KB Output is correct
39 Correct 156 ms 172792 KB Output is correct
40 Correct 153 ms 172664 KB Output is correct
41 Correct 153 ms 172664 KB Output is correct
42 Correct 124 ms 169972 KB Output is correct
43 Correct 119 ms 170020 KB Output is correct
44 Correct 124 ms 169908 KB Output is correct
45 Correct 151 ms 175608 KB Output is correct
46 Correct 149 ms 175736 KB Output is correct
47 Runtime error 521 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
48 Halted 0 ms 0 KB -