oj.uz

답안 #113720

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
113720 2019-05-28T04:48:28 Z mbfibat 버스 (JOI14_bus) C++14
100 / 100
 525 ms 35320 KB 
#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.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 7 ms 5120 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 6 ms 5120 KB Output is correct
8 Correct 7 ms 5120 KB Output is correct
9 Correct 6 ms 5120 KB Output is correct
10 Correct 7 ms 5120 KB Output is correct
11 Correct 9 ms 5248 KB Output is correct
12 Correct 8 ms 5248 KB Output is correct
13 Correct 7 ms 5248 KB Output is correct
14 Correct 8 ms 5248 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5248 KB Output is correct
2 Correct 50 ms 7936 KB Output is correct
3 Correct 48 ms 7820 KB Output is correct
4 Correct 10 ms 5376 KB Output is correct
5 Correct 11 ms 5392 KB Output is correct
6 Correct 10 ms 5248 KB Output is correct
7 Correct 44 ms 6904 KB Output is correct
8 Correct 6 ms 5120 KB Output is correct
9 Correct 45 ms 6904 KB Output is correct
10 Correct 49 ms 7928 KB Output is correct
11 Correct 44 ms 7160 KB Output is correct
12 Correct 46 ms 8188 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 293 ms 32640 KB Output is correct
2 Correct 294 ms 32648 KB Output is correct
3 Correct 288 ms 32608 KB Output is correct
4 Correct 304 ms 32632 KB Output is correct
5 Correct 299 ms 32632 KB Output is correct
6 Correct 429 ms 32504 KB Output is correct
7 Correct 374 ms 31864 KB Output is correct
8 Correct 308 ms 32376 KB Output is correct
9 Correct 303 ms 32620 KB Output is correct
10 Correct 445 ms 31696 KB Output is correct
11 Correct 380 ms 31392 KB Output is correct
12 Correct 425 ms 32192 KB Output is correct
13 Correct 415 ms 32248 KB Output is correct
14 Correct 445 ms 31992 KB Output is correct
15 Correct 421 ms 31628 KB Output is correct
16 Correct 93 ms 13816 KB Output is correct
17 Correct 79 ms 13816 KB Output is correct

Subtask #4
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 333 ms 35164 KB Output is correct
2 Correct 350 ms 34936 KB Output is correct
3 Correct 347 ms 35312 KB Output is correct
4 Correct 347 ms 35320 KB Output is correct
5 Correct 355 ms 34872 KB Output is correct
6 Correct 339 ms 35064 KB Output is correct
7 Correct 413 ms 34824 KB Output is correct
8 Correct 348 ms 35200 KB Output is correct
9 Correct 338 ms 35284 KB Output is correct
10 Correct 497 ms 34256 KB Output is correct
11 Correct 500 ms 34260 KB Output is correct
12 Correct 525 ms 34296 KB Output is correct
13 Correct 478 ms 34056 KB Output is correct
14 Correct 507 ms 34184 KB Output is correct
15 Correct 496 ms 34156 KB Output is correct
16 Correct 129 ms 15864 KB Output is correct