Submission #89285

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
89285	2018-12-11 10:50:19	Mouhanad_Hafez	Jakarta Skyscrapers (APIO15_skyscraper)	C++11	100 / 100	126 ms	20316 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;
    typedef pair<int, int> pii;
    int N, M, S, E;
    int D[30005];
    bool V[30005][200];
    vector <int> doge[30005];
    int main()
    {
      cin>>N>>M;
      for (int i=0;i<M;i++){
        int b, p;
        cin>>b>>p;
        if (p > 199 || !V[b][p]) doge[b].push_back(p);
        if (p < 200) V[b][p] = 1;
        if (!i) S = b;
        if (i == 1) E = b;
      }
      for (int i=0;i<N;i++) D[i] = 2e9;
      priority_queue <pii> que;
      D[S] = 0;
      que.push(make_pair(0, S));
      while (!que.empty()){
        int q = que.top().second, d = -que.top().first; que.pop();
        if (D[q] != d) continue;
        for (int p: doge[q]){
          for (int i=q-p;i>=0;i-=p){
            if (D[i] > d+(q-i)/p)
              D[i] = d+(q-i)/p, que.push(make_pair(-D[i], i));
            if (p < 200 && V[i][p]) break;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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