제출 #441712

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
441712	2021-07-05 21:25:38	dutch	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	87 ms	4928 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
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define DIJKSTRA if(d[v] > dist + w) q.push({-(d[v] = dist + w), v})
 
const int SQRT = 2, MAXN = 3e4, INF = 2e9;
vector<array<int, 2>> g[MAXN*SQRT];
vector<int> h[MAXN];
int n, m, b, p, s, t, d[MAXN*SQRT];
 
signed main(){
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
 
  for(int _=0; _<m; ++_){
    cin >> b >> p;
    if(_ == 0) s = b;
    if(_ == 1) t = b;
    int c = b * SQRT;
    if(p < SQRT) g[c].push_back({c+p, 0});
    else h[b].push_back(p);
  }
 
  priority_queue<array<int, 2>> q;
  fill(d, d+n*SQRT, INF);
  q.push({d[s*SQRT] = 0, s*SQRT});
 
  while(!q.empty()){
    int u = q.top()[1], dist = -q.top()[0];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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