Submission #25566

#	Time	Username	Problem	Language	Result	Execution time	Memory
25566		zigui	버스 (JOI14_bus)	C++14	100 / 100	443 ms	125368 KiB

bus

#include<stdio.h>
#include<queue>
#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(){}
	bus(int src, int dst, int p, int q):src(src), dst(dst), p(p), q(q){}
	int src, dst, p, q;
	bool operator<(const bus &l)const{
		return p < l.p;
	}
} D[MX*3];

deque<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{
//		for(pii c : T[d]) printf("%d %d\n", c.first, c.second);
//		printf("find : %d %d\n\n", c.q, (int)1e9);
		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);
	}
}

void insert(deque<pii> &X, pii c){
	if( X.empty() || X.front().second > c.second ) X.push_front(c);
}

int main()
{
	scanf("%d%d", &N, &M);
	for(int i = 1; i <= M; i++){
		scanf("%d%d%d%d", &a, &b, &c, &d);
		D[i] = bus(a, b, c, d);
	}
	sort(D+1, D+M+1);
	for(int i = M; i >= 1; i--){
		pii c = get_time(D[i]);
		insert(T[D[i].src], 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 (stderr)

bus.cpp: In function 'int main()':
bus.cpp:46: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:48: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:60:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
                 ^
bus.cpp:62:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
                  ^

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