제출 #1286819

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286819		kerem	버스 (JOI14_bus)	C++20	20 / 100	262 ms	32856 KiB

bus

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define pb push_back
#define emb emplace_back
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define N 100000
#define inf (int)86400000
typedef pair<int,int> ii;
typedef tuple<int,int,int> iii;

bool vis[N+5];
vector<ii> d[N+5];
vector<iii> g[N+5];

int bs(int i,int x){
	int l=0,r=d[i].size()-1;
	while(l<r){
		int mid=(l+r+1)/2;
		if(x>d[i][mid].fr)
			r=mid-1;
		else l=mid;
	}
	return max(x,d[i][l].sc);
}
void dfs(int x){
	vis[x]=1;
	for(auto [l,r,i]:g[x]){
		if(!vis[i]) dfs(i);
		d[x].emb(l,min(d[x].back().sc,bs(i,r)));
	}
}
void solve(){
	int n,m;
	cin >> n >> m;
	for(int i=0;i<m;i++){
		int a,b,x,y;
		cin >> a >> b >> x >> y;
		g[a].emb(x,y,b);
	}
	for(int i=1;i<n;i++){
		d[i].emb(inf,inf);
		sort(all(g[i]),greater<iii>());
	}
	vis[n]=1;
	d[n].emb(inf,0);
	dfs(1);
	int q;cin>> q;
	while(q--){
		int x;
		cin >> x;
		int l=0,r=d[1].size();
		while(l<r){
			int mid=(l+r)/2;
			if(d[1][mid].sc>x)
				l=mid+1;
			else r=mid;
		}
		if(l==(int)d[1].size()) cout << -1 << "\n";
		else cout << d[1][l].fr << "\n"; 
	}
}
int32_t main(){
	//~ freopen("hopscotch.in","r",stdin);
	//~ freopen("hopscotch.out","w",stdout);
	
	cout << fixed << setprecision(0);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	int test=1;
	//~ cin >> test;
	while(test--) solve();
}

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