Submission #25560

#	Time	Username	Problem	Language	Result	Execution time	Memory
25560		zigui	버스 (JOI14_bus)	C++14	0 / 100	456 ms	16068 KiB

bus

#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 (stderr)

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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 50