oj.uz

Submission #265362

# Submission time Handle Problem Language Result Execution time Memory
265362 2020-08-14T16:28:33 Z T0p_ Sightseeing (NOI14_sightseeing) C++14
15 / 25
 3500 ms 202684 KB 
#include<bits/stdc++.h>
using namespace std;

#define pb push_back

struct DATA
{
	int node, val;
	bool operator < (const DATA & o) const
	{
		return val < o.val;
	}	
};

int ans[500500];
priority_queue<DATA> heap;
vector<DATA> g[500500];

int main()
{
	int n, m, q;
	scanf(" %d %d %d",&n,&m,&q);
	while(m--)
	{
		int u, v, w;
		scanf(" %d %d %d",&u,&v,&w);
		g[u].pb({v, w}), g[v].pb({u, w});
	}
	heap.push({1, 1000000000});
	while(!heap.empty())
	{
		int nown = heap.top().node;
		int nowv = heap.top().val;
		heap.pop();
		for(auto x : g[nown])
		{
			int vv = min(nowv, x.val);
			if(vv > ans[x.node])
			{
				ans[x.node] = vv;
				heap.push({x.node, ans[x.node]});
			}
		}
	}
	while(q--)
	{
		int d;
		scanf(" %d",&d);
		printf("%d\n",ans[d]);
	}
	return 0;
}

Compilation message

sightseeing.cpp: In function 'int main()':
sightseeing.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 |  scanf(" %d %d %d",&n,&m,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sightseeing.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   26 |   scanf(" %d %d %d",&u,&v,&w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sightseeing.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |   scanf(" %d",&d);
      |   ~~~~~^~~~~~~~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 15096 KB Output is correct
2 Correct 40 ms 14584 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3474 ms 163760 KB Output is correct
2 Execution timed out 3566 ms 202684 KB Time limit exceeded