oj.uz

답안 #18534

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
18534 2016-02-08T08:59:09 Z choyi0521 버스 (JOI14_bus) C++14
85 / 100
 704 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());
		unique(t[i].begin(), 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 3 ms 26408 KB Output is correct
2 Correct 5 ms 26408 KB Output is correct
3 Correct 0 ms 26408 KB Output is correct
4 Correct 4 ms 26408 KB Output is correct
5 Correct 3 ms 26408 KB Output is correct
6 Correct 4 ms 26408 KB Output is correct
7 Correct 0 ms 26408 KB Output is correct
8 Correct 3 ms 26408 KB Output is correct
9 Correct 2 ms 26408 KB Output is correct
10 Correct 4 ms 26408 KB Output is correct
11 Correct 4 ms 26540 KB Output is correct
12 Correct 6 ms 26540 KB Output is correct
13 Correct 9 ms 26544 KB Output is correct
14 Correct 7 ms 26540 KB Output is correct

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 26408 KB Output is correct
2 Correct 53 ms 26408 KB Output is correct
3 Correct 44 ms 26408 KB Output is correct
4 Correct 9 ms 26408 KB Output is correct
5 Correct 9 ms 26408 KB Output is correct
6 Correct 12 ms 26408 KB Output is correct
7 Incorrect 39 ms 26408 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 618 ms 52148 KB Output is correct
2 Correct 553 ms 52148 KB Output is correct
3 Correct 584 ms 52148 KB Output is correct
4 Correct 563 ms 52148 KB Output is correct
5 Correct 517 ms 52148 KB Output is correct
6 Correct 546 ms 52156 KB Output is correct
7 Correct 442 ms 51752 KB Output is correct
8 Correct 602 ms 52372 KB Output is correct
9 Correct 551 ms 52148 KB Output is correct
10 Correct 572 ms 53168 KB Output is correct
11 Correct 568 ms 53124 KB Output is correct
12 Correct 559 ms 53208 KB Output is correct
13 Correct 557 ms 53208 KB Output is correct
14 Correct 572 ms 53124 KB Output is correct
15 Correct 502 ms 53128 KB Output is correct
16 Correct 184 ms 44936 KB Output is correct
17 Correct 139 ms 38816 KB Output is correct

Subtask #4
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 522 ms 52148 KB Output is correct
2 Correct 502 ms 52148 KB Output is correct
3 Correct 626 ms 52148 KB Output is correct
4 Correct 595 ms 52148 KB Output is correct
5 Correct 641 ms 52148 KB Output is correct
6 Correct 601 ms 52156 KB Output is correct
7 Correct 593 ms 51752 KB Output is correct
8 Correct 593 ms 52148 KB Output is correct
9 Correct 598 ms 52148 KB Output is correct
10 Correct 492 ms 53168 KB Output is correct
11 Correct 658 ms 53124 KB Output is correct
12 Correct 646 ms 53128 KB Output is correct
13 Correct 704 ms 53128 KB Output is correct
14 Correct 565 ms 53124 KB Output is correct
15 Correct 475 ms 53128 KB Output is correct
16 Correct 211 ms 44944 KB Output is correct