Submission #108296

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
108296	2019-04-28 13:14:29	maruii	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	686 ms	3620 KiB

skyscraper

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second
priority_queue<pii, vector<pii>, greater<pii> > pq;
int dst[30000];
vector<int> edge[30000];
int main(){
  ios_base::sync_with_stdio(0), cin.tie(0);
  int N, M, st, ed; cin>>N>>M;
  for(int i=0; i<M; ++i){
    int b,p; cin>>b>>p;
    edge[b].push_back(p);
    if(!i) st = b;
    else if(i==1) ed = b;
  }
  fill(dst, dst+N, 1e9);
  pq.emplace(0, st); dst[st] = 0;
  while(pq.size()){
    auto x = pq.top(); pq.pop();
    if(x.ff != dst[x.ss]) continue;
    for(auto p: edge[x.ss]){
      for(int j=0; x.ss+p*j<N; ++j){
        if(dst[x.ss+p*j] > x.ff + j){
          dst[x.ss+p*j] = x.ff + j;
          pq.emplace(x.ff + j, x.ss+p*j);
        }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:21:29: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
  pq.emplace(0, st); dst[st] = 0;
                     ~~~~~~~~^~~
skyscraper.cpp:41:15: warning: 'ed' may be used uninitialized in this function [-Wmaybe-uninitialized]
  cout<<(dst[ed]==1e9?-1:dst[ed]);
         ~~~~~~^

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 43 / 43