oj.uz

답안 #18536

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
18536 2016-02-08T09:05:10 Z choyi0521 버스 (JOI14_bus) C++14
100 / 100
 689 ms 53208 KB 
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N = 1e5,MAX_M=3e5,MAX_Q=1e5;
int n, m,q,cnt,res[MAX_Q];
vector<int> t[MAX_N+1],idx[MAX_N+1],adj[MAX_M*2];
pair<int, int> query[MAX_Q];
struct st {
	int a, b, x, y;
}s[MAX_M];
bool ck[MAX_M * 2];
int maxi=-1;
void dfs(int h) {
	if (h < idx[1].size()) maxi = max(maxi, t[1][h]);
	if (ck[h]) return;
	ck[h] = true;
	for (auto t : adj[h]) dfs(t);
}
int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++){
		scanf("%d %d %d %d", &s[i].a, &s[i].b, &s[i].x, &s[i].y);
		t[s[i].a].push_back(s[i].x);
		t[s[i].b].push_back(s[i].y);
	}
	for (int i = 1; i <= n; i++) {
		sort(t[i].begin(), t[i].end());
		t[i].erase(unique(t[i].begin(), t[i].end()),t[i].end());
		for (int j = 0; j < t[i].size(); j++) {
			if (j) adj[cnt].push_back(cnt - 1);
			idx[i].push_back(cnt++);
		}
	}
	for (int i = 0; i < m; i++) {
		int a = lower_bound(t[s[i].a].begin(), t[s[i].a].end(), s[i].x) - t[s[i].a].begin(),
			b = lower_bound(t[s[i].b].begin(), t[s[i].b].end(), s[i].y) - t[s[i].b].begin();
		adj[idx[s[i].b][b]].push_back(idx[s[i].a][a]);
	}
	scanf("%d", &q);
	for (int i = 0; i < q; i++) {
		scanf("%d",&query[i].first);
		query[i].second=i;
	}
	sort(query, query + q);
	for (int i = 0; i < q; i++) {
		int a = upper_bound(t[n].begin(), t[n].end(), query[i].first) - t[n].begin() - 1;
		if(a>=0) dfs(idx[n][a]);
		res[query[i].second] = maxi;
	}
	for (int i = 0; i < q; i++) printf("%d\n", res[i]);
	return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 26408 KB Output is correct
2 Correct 51 ms 26408 KB Output is correct
3 Correct 47 ms 26408 KB Output is correct
4 Correct 6 ms 26408 KB Output is correct
5 Correct 8 ms 26408 KB Output is correct
6 Correct 6 ms 26408 KB Output is correct
7 Correct 39 ms 26408 KB Output is correct
8 Correct 3 ms 26408 KB Output is correct
9 Correct 40 ms 26408 KB Output is correct
10 Correct 50 ms 26540 KB Output is correct
11 Correct 48 ms 26540 KB Output is correct
12 Correct 34 ms 26540 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 564 ms 52148 KB Output is correct
2 Correct 558 ms 52148 KB Output is correct
3 Correct 568 ms 52148 KB Output is correct
4 Correct 416 ms 52148 KB Output is correct
5 Correct 594 ms 52148 KB Output is correct
6 Correct 553 ms 52156 KB Output is correct
7 Correct 605 ms 51752 KB Output is correct
8 Correct 629 ms 52372 KB Output is correct
9 Correct 568 ms 52148 KB Output is correct
10 Correct 570 ms 53168 KB Output is correct
11 Correct 546 ms 53128 KB Output is correct
12 Correct 617 ms 53208 KB Output is correct
13 Correct 646 ms 53208 KB Output is correct
14 Correct 593 ms 53124 KB Output is correct
15 Correct 557 ms 53128 KB Output is correct
16 Correct 186 ms 44940 KB Output is correct
17 Correct 99 ms 38816 KB Output is correct

Subtask #4
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 618 ms 52148 KB Output is correct
2 Correct 592 ms 52148 KB Output is correct
3 Correct 577 ms 52148 KB Output is correct
4 Correct 579 ms 52148 KB Output is correct
5 Correct 587 ms 52148 KB Output is correct
6 Correct 655 ms 52156 KB Output is correct
7 Correct 606 ms 51752 KB Output is correct
8 Correct 569 ms 52148 KB Output is correct
9 Correct 548 ms 52148 KB Output is correct
10 Correct 666 ms 53168 KB Output is correct
11 Correct 689 ms 53128 KB Output is correct
12 Correct 634 ms 53128 KB Output is correct
13 Correct 633 ms 53128 KB Output is correct
14 Correct 620 ms 53124 KB Output is correct
15 Correct 638 ms 53128 KB Output is correct
16 Correct 208 ms 44940 KB Output is correct