oj.uz

Submission #425447

# Submission time Handle Problem Language Result Execution time Memory
425447 2021-06-13T03:58:28 Z errorgorn Sightseeing (NOI14_sightseeing) C++17
15 / 25
 3500 ms 248964 KB 
#include <cstdio>
#include <vector>
#include <utility>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int,int> ii;
vector<ii> al[500005];
vector<ii>::iterator it;
priority_queue<ii> pq;
int v,e,q,w[500005];
int main(){
  //freopen("input.txt","r",stdin);
  int a,b,c;
  scanf("%d%d%d",&v,&e,&q);
  memset(w,-1,sizeof(w));
  w[1]=100000000;
  pq.push(ii (100000000,1));
  while (e--){
    scanf("%d%d%d",&a,&b,&c);
    al[a].push_back( ii(b,c));
    al[b].push_back(ii (a,c));
  }
  while (!pq.empty()){
    a=pq.top().first,b=pq.top().second,pq.pop();
    if (w[b]!=a) continue;
    for (it=al[b].begin();it!=al[b].end();it++){
      if (w[(*it).first]<min(a,(*it).second)){
        w[(*it).first]=min(a,(*it).second);
        pq.push(ii (w[(*it).first],(*it).first));
      }
    }
  }
  while (q--){
    scanf("%d",&a);
    printf("%d\n",w[a]);
  }
}

Compilation message

sightseeing.cpp: In function 'int main()':
sightseeing.cpp:16:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |   scanf("%d%d%d",&v,&e,&q);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
sightseeing.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     scanf("%d%d%d",&a,&b,&c);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
sightseeing.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     scanf("%d",&a);
      |     ~~~~~^~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 13900 KB Output is correct
2 Correct 8 ms 13900 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14160 KB Output is correct
2 Correct 9 ms 14028 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 16808 KB Output is correct
2 Correct 39 ms 16252 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3113 ms 165272 KB Output is correct
2 Execution timed out 3602 ms 248964 KB Time limit exceeded