Submission #25584

#	Time	Username	Problem	Language	Result	Execution time	Memory
25584		suhgyuho_william	버스 (JOI14_bus)	C++14	100 / 100	303 ms	12224 KiB

bus

#include <bits/stdc++.h>

#define lld long long
#define pp pair<int,int>
#define pb push_back
#define MOD 1000000007
#define left lleft
#define right rright
#define INF 2000000000
#define Linf 1000000000000000000LL
#define next nnext
#define minus mminus

using namespace std;

int N,M,Q,ans;
struct data{
	int x,y,tx,ty;
}edge[300002];
vector<pair<int,pp>> d[100002];
priority_queue<pp> q;
vector<int> print;

int main(){
	scanf("%d %d",&N,&M);
	for(int i=1; i<=M; i++){
		scanf("%d %d %d %d",&edge[i].x,&edge[i].y,&edge[i].tx,&edge[i].ty);
		if(edge[i].x == 1) print.pb(edge[i].tx);
	}
	sort(edge+1,edge+M+1,[&](data &x,data &y){
		return x.ty < y.ty;
	});
	sort(print.begin(),print.end());
	for(int i=0; i<print.size(); i++) d[1].pb({print[i],{i,i}});
	for(int i=1; i<=M; i++){
		int x,y,tx,ty;
		x = edge[i].x; y = edge[i].y; tx = edge[i].tx; ty = edge[i].ty;
		if(d[x].size() == 0 || d[x][0].first > tx) continue;
		int l,r,t;
		l = 0; r = d[x].size()-1;
		while(l <= r){
			int mid = (l+r)/2;
			if(d[x][mid].first <= tx){
				t = mid;
				l = mid+1;
			}else r = mid-1;
		}
		int e = d[x][t].second.second;
		if(d[y].size() == 0 || d[y].back().second.second < e){
            int tt;
            if(d[y].size() == 0) tt = 0;
            else tt = d[y].back().second.second+1;
			d[y].pb({ty,{tt,e}});
		}
	}

	scanf("%d",&Q);
	for(int i=1; i<=Q; i++){
		int query;
		scanf("%d",&query);
		if(d[N].size() == 0 || query < d[N][0].first){
			ans = -1;
		}else{
			int l,r,t;
			l = 0; r = d[N].size()-1;
			while(l <= r){
				int mid = (l+r)/2;
				if(d[N][mid].first <= query){
					t = mid;
					l = mid+1;
				}else r = mid-1;
			}
			t = d[N][t].second.second;
			ans = print[t];
		}
		printf("%d\n",ans);
	}

	return 0;
}

Compilation message (stderr)

bus.cpp: In function 'int main()':
bus.cpp:34:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<print.size(); i++) d[1].pb({print[i],{i,i}});
                ^
bus.cpp:25:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&N,&M);
                      ^
bus.cpp:27:69: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d",&edge[i].x,&edge[i].y,&edge[i].tx,&edge[i].ty);
                                                                     ^
bus.cpp:57:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&Q);
                ^
bus.cpp:60:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&query);
                     ^
bus.cpp:73:14: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
    t = d[N][t].second.second;
              ^
bus.cpp:48:17: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int e = d[x][t].second.second;
                 ^

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