oj.uz

Submission #25560

# Submission time Handle Problem Language Result Execution time Memory
25560 2017-06-23T05:03:44 Z zigui 버스 (JOI14_bus) C++14
0 / 100
 456 ms 16068 KB 
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MX = 100005;

struct bus{
	bus(int dst, int p, int q):dst(dst), p(p), q(q){}
	int dst, p, q;
};

vector<bus> G[MX];
vector<pii> T[MX];
int N, M;
int a, b, c, d;

pii get_time(bus c){
	int d = c.dst;
	if( d == N ) return pii(c.p, c.q);
	else{
		auto it = lower_bound(T[d].begin(), T[d].end(), pii(c.q, -1e9));
		if( it == T[d].end() ) return pii(c.p, 1e9);
		else return pii(c.p, it->second);
	}
}

int main()
{
	scanf("%d%d", &N, &M);
	for(int i = 1; i <= M; i++){
		scanf("%d%d%d%d", &a, &b, &c, &d);
		G[a].emplace_back(b, c, d);
	}

	for(int i = N-1; i >= 1; i--){
		vector<pii> L;
		for(bus c : G[i]){
			L.push_back(get_time(c));
		}
		sort(L.begin(), L.end());
		for(pii c : L){
			while(T[i].size() && T[i].back().second > c.second ) T[i].pop_back();
			T[i].push_back(c);
		}
	}
	vector<pii> X;
	for(pii c : T[1]) X.emplace_back(c.second, c.first);
	int Q;
	scanf("%d", &Q);
	for(int i = 1; i <= Q; i++){
		scanf("%d", &a);
		auto it = upper_bound(X.begin(), X.end(), pii(a, 1e9));
		if( it == X.begin() ) printf("-1\n");
		else printf("%d\n", (--it)->second);
	}
}

Compilation message

bus.cpp: In function 'int main()':
bus.cpp:36:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
                       ^
bus.cpp:38:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &a, &b, &c, &d);
                                    ^
bus.cpp:56:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
                 ^
bus.cpp:58:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
                  ^

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5864 KB Output is correct
2 Correct 0 ms 5864 KB Output is correct
3 Correct 0 ms 5864 KB Output is correct
4 Correct 0 ms 5864 KB Output is correct
5 Correct 3 ms 5864 KB Output is correct
6 Correct 3 ms 5864 KB Output is correct
7 Correct 0 ms 5864 KB Output is correct
8 Correct 3 ms 5864 KB Output is correct
9 Incorrect 0 ms 5864 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5864 KB Output is correct
2 Correct 29 ms 5864 KB Output is correct
3 Correct 33 ms 5864 KB Output is correct
4 Correct 3 ms 5864 KB Output is correct
5 Correct 3 ms 5864 KB Output is correct
6 Incorrect 0 ms 5864 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 16024 KB Output is correct
2 Correct 443 ms 16028 KB Output is correct
3 Correct 379 ms 16028 KB Output is correct
4 Correct 339 ms 16028 KB Output is correct
5 Correct 393 ms 16028 KB Output is correct
6 Correct 409 ms 16068 KB Output is correct
7 Correct 296 ms 13928 KB Output is correct
8 Correct 259 ms 15720 KB Output is correct
9 Correct 369 ms 16040 KB Output is correct
10 Correct 226 ms 12340 KB Output is correct
11 Incorrect 219 ms 12476 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 393 ms 16024 KB Output is correct
2 Correct 386 ms 16028 KB Output is correct
3 Correct 426 ms 16028 KB Output is correct
4 Correct 443 ms 16028 KB Output is correct
5 Correct 456 ms 16028 KB Output is correct
6 Correct 299 ms 16068 KB Output is correct
7 Incorrect 333 ms 13928 KB Output isn't correct
8 Halted 0 ms 0 KB -