Submission #1286850

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286850		kerem	버스 (JOI14_bus)	C++20	100 / 100	140 ms	29276 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;

int ind[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,int t){
	for(;ind[x]<(int)g[x].size();ind[x]++){
		int l,r,i;
		tie(l,r,i)=g[x][ind[x]];
		if(l<t) break;
		dfs(i,r);
		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>());
	}
	ind[n]=g[n].size();
	d[n].emb(inf,0);
	dfs(1,0);
	int q;cin>> q;
	while(q--){
		int x;
		cin >> x;
		int l=1,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: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 50 / 50