oj.uz

Submission #39446

# Submission time Handle Problem Language Result Execution time Memory
39446 2018-01-15T07:54:49 Z 14kg 버스 (JOI14_bus) C++11
100 / 100
 533 ms 22336 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6640 KB Output is correct
2 Correct 0 ms 6640 KB Output is correct
3 Correct 0 ms 6640 KB Output is correct
4 Correct 0 ms 6640 KB Output is correct
5 Correct 0 ms 6640 KB Output is correct
6 Correct 0 ms 6640 KB Output is correct
7 Correct 0 ms 6640 KB Output is correct
8 Correct 0 ms 6640 KB Output is correct
9 Correct 0 ms 6640 KB Output is correct
10 Correct 0 ms 6640 KB Output is correct
11 Correct 0 ms 6780 KB Output is correct
12 Correct 0 ms 6780 KB Output is correct
13 Correct 0 ms 6780 KB Output is correct
14 Correct 0 ms 6780 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6640 KB Output is correct
2 Correct 39 ms 8276 KB Output is correct
3 Correct 43 ms 8276 KB Output is correct
4 Correct 3 ms 6912 KB Output is correct
5 Correct 3 ms 6912 KB Output is correct
6 Correct 3 ms 6912 KB Output is correct
7 Correct 33 ms 8276 KB Output is correct
8 Correct 0 ms 6640 KB Output is correct
9 Correct 43 ms 8276 KB Output is correct
10 Correct 56 ms 8324 KB Output is correct
11 Correct 59 ms 8324 KB Output is correct
12 Correct 56 ms 8324 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 21056 KB Output is correct
2 Correct 346 ms 21056 KB Output is correct
3 Correct 363 ms 21056 KB Output is correct
4 Correct 343 ms 21056 KB Output is correct
5 Correct 409 ms 21056 KB Output is correct
6 Correct 336 ms 21056 KB Output is correct
7 Correct 339 ms 21056 KB Output is correct
8 Correct 319 ms 21056 KB Output is correct
9 Correct 326 ms 21056 KB Output is correct
10 Correct 333 ms 21056 KB Output is correct
11 Correct 299 ms 21056 KB Output is correct
12 Correct 323 ms 21056 KB Output is correct
13 Correct 309 ms 21056 KB Output is correct
14 Correct 303 ms 21056 KB Output is correct
15 Correct 319 ms 21056 KB Output is correct
16 Correct 103 ms 9796 KB Output is correct
17 Correct 86 ms 9796 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 22336 KB Output is correct
2 Correct 433 ms 22336 KB Output is correct
3 Correct 426 ms 22336 KB Output is correct
4 Correct 463 ms 22336 KB Output is correct
5 Correct 533 ms 22336 KB Output is correct
6 Correct 449 ms 22336 KB Output is correct
7 Correct 399 ms 22336 KB Output is correct
8 Correct 439 ms 22336 KB Output is correct
9 Correct 436 ms 22336 KB Output is correct
10 Correct 416 ms 22336 KB Output is correct
11 Correct 389 ms 22336 KB Output is correct
12 Correct 389 ms 22336 KB Output is correct
13 Correct 433 ms 22336 KB Output is correct
14 Correct 376 ms 22336 KB Output is correct
15 Correct 396 ms 22336 KB Output is correct
16 Correct 116 ms 10816 KB Output is correct