Submission #39446

#	Time	Username	Problem	Language	Result	Execution time	Memory
39446		14kg	버스 (JOI14_bus)	C++11	100 / 100	533 ms	22336 KiB

bus

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <functional>
#define N 100001
#define INF 999999999
#define min2(x,y) (x<y?x:y)
#define max2(x,y) (x>y?x:y)

using namespace std;
typedef pair<int, pair<int, int> > pip;
int n, m, q_len, d[N], out[N];
pair<pair<int, int>, pair<int, int> > bus[300001];
priority_queue<pair<int, pair<int,int> >, vector<pair<int, pair<int,int> > >, greater<pair<int, pair<int,int> > > > Q_push;
priority_queue<pair<int, pip>, vector<pair<int, pip> >, greater<pair<int, pip> > > Q_pop;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > Q_out;

int main() {
	int x, y, tx, ty, t;
	pair<int, pair<int,int> > temp1;
	pair<int, pip> temp2;
	pair<int, int> temp3;

	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) d[i] = -1;
	for (int i = 1; i <= m; i++) {
		scanf("%d %d %d %d", &x, &y, &tx, &ty);
		Q_pop.push({ tx,{x,{y,ty}} });
	}
	scanf("%d", &q_len);
	for (int i = 1; i <= q_len; i++) {
		scanf("%d", &x);
		Q_out.push({ x,i });
	}

	Q_push.push({ INF,{0,0} }), Q_pop.push({ INF, { 0,{0,0} } }), Q_out.push({ INF,0 });
	while (1) {
		t = min2(Q_push.top().first, min2(Q_pop.top().first, Q_out.top().first));
		if (t == INF) break;

		d[1] = t;
		while (Q_push.top().first == t) {
			temp1 = Q_push.top(), Q_push.pop();
			d[temp1.second.first] = max2(d[temp1.second.first], temp1.second.second);
		}
		while (Q_pop.top().first == t) {
			temp2 = Q_pop.top(), Q_pop.pop();
			Q_push.push({ temp2.second.second.second,{ temp2.second.second.first,d[temp2.second.first] } });
		}
		while (Q_out.top().first == t) {
			temp3 = Q_out.top(), Q_out.pop();
			out[temp3.second] = d[n];
		}
	}
	for (int i = 1; i <= q_len; i++) printf("%d\n", out[i]);
}

Compilation message (stderr)

bus.cpp: In function 'int main()':
bus.cpp:25:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
                        ^
bus.cpp:28:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d", &x, &y, &tx, &ty);
                                         ^
bus.cpp:31:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q_len);
                     ^
bus.cpp:33:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
                  ^

• Subtask 1: 20 / 20
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 50 / 50