oj.uz

답안 #838447

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
838447 2023-08-27T00:56:51 Z 8pete8 Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 367 ms 262144 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define pb push_back
#define all(x) x.begin(),x.end()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define p push
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
const int mxn=3*1e4,mod=998244353,lg=42,root=80,inf=1e9;
void setIO(string name) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}
int dist[(2*mxn*(root+1))+10];
vector<pii>adj[(2*mxn*(root+1))+10];
bitset<(2*mxn*(root+1))+10>vis;
int n,m;
//make dummy node
// n orginal + n node for each root(n)
//node more than root id = mxn*ith+starting point
void init(){
    for(int i=1;i<=min(n,root);i++){
        for(int j=0;j<n;j++){
            adj[(mxn*i)+j].pb({j,0});//going down
        }
        for(int j=i;j<n;j++){
            //buid=ld edge for each i
            adj[(mxn*i)+j].pb({(mxn*i)+(j-i),1});
            adj[(mxn*i)+(j-i)].pb({(mxn*i)+j,1});
        }
    }
}
int32_t main(){
    fastio
    cin>>n>>m;
    int end;
    init();
    fill(dist,dist+(2*mxn*(root+1)),inf);
    priority_queue<pii,vector<pii>,greater<pii>>pq;
    for(int i=0;i<m;i++){
        int st,p;cin>>st>>p;
        if(i==1)end=st;
        if(i==0)pq.push({0,st}),dist[st]=0;
        if(p<=root)adj[st].pb({(p*mxn)+st,0});
        else{
            for(int j=1;(j*p)+st<n;j++){
                adj[st].pb({(j*p)+st,j});
                //adj[(j*p)+st].pb({st,j});
            }
            for(int j=1;st-(j*p)>=0;j++){
                adj[st].pb({st-(j*p),j});
                //adj[st-(j*p)].pb({st,j});
            }
            //connect normal edge
        }
        //input
    }
    //dijkstra
    while(!pq.empty()){
        int cur=pq.top().s;
        pq.pop();
        for(auto i:adj[cur]){
            if(dist[i.f]>dist[cur]+i.s){
                dist[i.f]=dist[cur]+i.s;
                pq.push({dist[i.f],i.f});
            }
        }
    }
    cout<<((dist[end]==inf)?-1:dist[end]);
    return 0;
}

Compilation message

skyscraper.cpp: In function 'void setIO(std::string)':
skyscraper.cpp:31:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:32:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp: In function 'int32_t main()':
skyscraper.cpp:89:21: warning: 'end' may be used uninitialized in this function [-Wmaybe-uninitialized]
   89 |     cout<<((dist[end]==inf)?-1:dist[end]);
      |             ~~~~~~~~^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 133464 KB Output is correct
2 Correct 57 ms 133452 KB Output is correct
3 Correct 62 ms 133452 KB Output is correct
4 Correct 56 ms 133396 KB Output is correct
5 Correct 56 ms 133380 KB Output is correct
6 Correct 55 ms 133548 KB Output is correct
7 Correct 59 ms 133380 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 133440 KB Output is correct
2 Correct 57 ms 133424 KB Output is correct
3 Correct 58 ms 133392 KB Output is correct
4 Correct 57 ms 133440 KB Output is correct
5 Correct 57 ms 133392 KB Output is correct
6 Correct 57 ms 133432 KB Output is correct
7 Correct 60 ms 133376 KB Output is correct
8 Correct 59 ms 133380 KB Output is correct
9 Correct 58 ms 133556 KB Output is correct
10 Correct 59 ms 133760 KB Output is correct
11 Correct 60 ms 133740 KB Output is correct
12 Correct 60 ms 133720 KB Output is correct
13 Correct 61 ms 133836 KB Output is correct
14 Correct 59 ms 133732 KB Output is correct
15 Correct 65 ms 133756 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 133436 KB Output is correct
2 Correct 57 ms 133416 KB Output is correct
3 Correct 57 ms 133348 KB Output is correct
4 Correct 59 ms 133460 KB Output is correct
5 Correct 59 ms 133456 KB Output is correct
6 Correct 64 ms 133416 KB Output is correct
7 Correct 61 ms 133424 KB Output is correct
8 Correct 58 ms 133492 KB Output is correct
9 Correct 59 ms 133560 KB Output is correct
10 Correct 59 ms 133644 KB Output is correct
11 Correct 60 ms 133708 KB Output is correct
12 Correct 65 ms 133800 KB Output is correct
13 Correct 61 ms 133676 KB Output is correct
14 Correct 62 ms 133792 KB Output is correct
15 Correct 60 ms 133708 KB Output is correct
16 Correct 59 ms 134024 KB Output is correct
17 Correct 68 ms 136180 KB Output is correct
18 Correct 72 ms 139996 KB Output is correct
19 Correct 74 ms 140876 KB Output is correct
20 Correct 73 ms 140944 KB Output is correct
21 Correct 61 ms 134844 KB Output is correct
22 Correct 70 ms 139980 KB Output is correct
23 Correct 73 ms 139316 KB Output is correct
24 Correct 74 ms 140544 KB Output is correct
25 Correct 74 ms 140964 KB Output is correct
26 Correct 74 ms 140860 KB Output is correct
27 Correct 77 ms 140908 KB Output is correct
28 Correct 74 ms 140944 KB Output is correct
29 Correct 76 ms 140912 KB Output is correct
30 Correct 75 ms 140932 KB Output is correct
31 Correct 75 ms 140908 KB Output is correct
32 Correct 75 ms 140872 KB Output is correct
33 Correct 86 ms 141076 KB Output is correct
34 Correct 85 ms 140964 KB Output is correct

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 133488 KB Output is correct
2 Correct 56 ms 133448 KB Output is correct
3 Correct 57 ms 133456 KB Output is correct
4 Correct 57 ms 133456 KB Output is correct
5 Correct 56 ms 133464 KB Output is correct
6 Correct 59 ms 133464 KB Output is correct
7 Correct 57 ms 133452 KB Output is correct
8 Correct 58 ms 133500 KB Output is correct
9 Correct 58 ms 133572 KB Output is correct
10 Correct 58 ms 133648 KB Output is correct
11 Correct 59 ms 133716 KB Output is correct
12 Correct 59 ms 133676 KB Output is correct
13 Correct 59 ms 133780 KB Output is correct
14 Correct 61 ms 133812 KB Output is correct
15 Correct 60 ms 133812 KB Output is correct
16 Correct 60 ms 134092 KB Output is correct
17 Correct 66 ms 136224 KB Output is correct
18 Correct 70 ms 139912 KB Output is correct
19 Correct 82 ms 141084 KB Output is correct
20 Correct 74 ms 140856 KB Output is correct
21 Correct 62 ms 134732 KB Output is correct
22 Correct 71 ms 140072 KB Output is correct
23 Correct 71 ms 139332 KB Output is correct
24 Correct 75 ms 140536 KB Output is correct
25 Correct 75 ms 140916 KB Output is correct
26 Correct 75 ms 140860 KB Output is correct
27 Correct 74 ms 140832 KB Output is correct
28 Correct 76 ms 140900 KB Output is correct
29 Correct 88 ms 140948 KB Output is correct
30 Correct 73 ms 140876 KB Output is correct
31 Correct 75 ms 140884 KB Output is correct
32 Correct 73 ms 140860 KB Output is correct
33 Correct 80 ms 140884 KB Output is correct
34 Correct 79 ms 140960 KB Output is correct
35 Correct 80 ms 139296 KB Output is correct
36 Correct 71 ms 137492 KB Output is correct
37 Correct 95 ms 141852 KB Output is correct
38 Correct 92 ms 141860 KB Output is correct
39 Correct 94 ms 141756 KB Output is correct
40 Correct 93 ms 141740 KB Output is correct
41 Correct 92 ms 141796 KB Output is correct
42 Correct 86 ms 141228 KB Output is correct
43 Correct 76 ms 141268 KB Output is correct
44 Correct 83 ms 141340 KB Output is correct
45 Correct 93 ms 144768 KB Output is correct
46 Correct 97 ms 144836 KB Output is correct

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 133460 KB Output is correct
2 Correct 60 ms 133452 KB Output is correct
3 Correct 59 ms 133452 KB Output is correct
4 Correct 58 ms 133416 KB Output is correct
5 Correct 59 ms 133336 KB Output is correct
6 Correct 58 ms 133432 KB Output is correct
7 Correct 58 ms 133448 KB Output is correct
8 Correct 58 ms 133500 KB Output is correct
9 Correct 60 ms 133580 KB Output is correct
10 Correct 58 ms 133740 KB Output is correct
11 Correct 59 ms 133704 KB Output is correct
12 Correct 58 ms 133772 KB Output is correct
13 Correct 59 ms 133780 KB Output is correct
14 Correct 59 ms 133812 KB Output is correct
15 Correct 60 ms 133696 KB Output is correct
16 Correct 66 ms 134024 KB Output is correct
17 Correct 67 ms 136188 KB Output is correct
18 Correct 72 ms 139976 KB Output is correct
19 Correct 73 ms 140936 KB Output is correct
20 Correct 72 ms 140876 KB Output is correct
21 Correct 64 ms 134788 KB Output is correct
22 Correct 74 ms 140204 KB Output is correct
23 Correct 76 ms 139376 KB Output is correct
24 Correct 76 ms 140520 KB Output is correct
25 Correct 77 ms 140872 KB Output is correct
26 Correct 77 ms 140940 KB Output is correct
27 Correct 74 ms 140948 KB Output is correct
28 Correct 83 ms 140980 KB Output is correct
29 Correct 78 ms 140924 KB Output is correct
30 Correct 75 ms 140936 KB Output is correct
31 Correct 75 ms 140876 KB Output is correct
32 Correct 75 ms 140876 KB Output is correct
33 Correct 80 ms 140952 KB Output is correct
34 Correct 79 ms 140928 KB Output is correct
35 Correct 80 ms 139192 KB Output is correct
36 Correct 68 ms 137480 KB Output is correct
37 Correct 92 ms 141836 KB Output is correct
38 Correct 93 ms 141792 KB Output is correct
39 Correct 91 ms 141908 KB Output is correct
40 Correct 91 ms 141844 KB Output is correct
41 Correct 95 ms 141772 KB Output is correct
42 Correct 77 ms 141260 KB Output is correct
43 Correct 76 ms 141280 KB Output is correct
44 Correct 76 ms 141236 KB Output is correct
45 Correct 92 ms 144676 KB Output is correct
46 Correct 92 ms 144808 KB Output is correct
47 Correct 266 ms 184992 KB Output is correct
48 Correct 265 ms 222156 KB Output is correct
49 Correct 277 ms 229984 KB Output is correct
50 Correct 277 ms 239228 KB Output is correct
51 Correct 340 ms 248768 KB Output is correct
52 Correct 353 ms 248692 KB Output is correct
53 Correct 297 ms 246476 KB Output is correct
54 Correct 291 ms 246096 KB Output is correct
55 Correct 299 ms 246108 KB Output is correct
56 Correct 307 ms 247268 KB Output is correct
57 Correct 367 ms 246180 KB Output is correct
58 Correct 309 ms 246588 KB Output is correct
59 Correct 302 ms 246720 KB Output is correct
60 Correct 328 ms 247180 KB Output is correct
61 Correct 329 ms 246996 KB Output is correct
62 Correct 311 ms 249264 KB Output is correct
63 Runtime error 289 ms 262144 KB Execution killed with signal 9
64 Halted 0 ms 0 KB -