제출 #113720

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
113720		mbfibat	버스 (JOI14_bus)	C++14	100 / 100	525 ms	35320 KiB

bus

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> ii;
typedef pair<int,ii> iii;
int n,m;
int q;
set<iii> AdjList[100001];
ii Q[100001];
int Q_res[100001];
int res = -1;

void bfs(int t)
{
	queue<ii> CurrList;
	CurrList.push(ii(n,t));
	//cerr << "cur t: " << t << '\n';
	while(!CurrList.empty())
	{
		int u = CurrList.front().first;
		int tt = CurrList.front().second;
		//cerr << u << '\n';
		CurrList.pop();
		set<iii>::iterator z1;
		for (z1 = AdjList[u].begin();z1 != AdjList[u].end();z1++)
		{
			int cur_t = (*z1).first;
			//cerr << cur_t << '\n';
			if (cur_t <= tt)
			{
				int v = (*z1).second.first;
				int w = (*z1).second.second;
				//cerr << v << ' ' << w << '\n';
				if (v == 1)
					res = max(res,w);			
				else
					CurrList.push(ii(v,w));
			}
			else
				break;
		}
		AdjList[u].erase(AdjList[u].begin(),z1);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	for (int i=1;i<=m;i++)
	{
		int u,v,a,b;
		cin >> u >> v >> a >> b;
		AdjList[v].insert(iii(b,ii(u,a)));
	}
	cin >> q;
	for (int i=1;i<=q;i++)
	{
		cin	>> Q[i].first;
		Q[i].second = i;
	}
	sort(Q+1,Q+1+q);
	for (int i=1;i<=q;i++)
	{
		int cur_t = Q[i].first;
		int id = Q[i].second;
		bfs(cur_t);
		Q_res[id] = res;
	} 	
	for (int i=1;i<=q;i++)
		cout << Q_res[i] << '\n';
}

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