oj.uz

Submission #54688

# Submission time Handle Problem Language Result Execution time Memory
54688 2018-07-04T15:35:00 Z ksun48 Long Mansion (JOI17_long_mansion) C++14
10 / 100
 3000 ms 113624 KB 
#include <bits/stdc++.h>
using namespace std;


//  0|   1|   2|   3|   4|   6|
//    23    1    1    3    4
vector<int> solve(int n, vector<int> walls, vector<vector<int> > keys){
	// keys range from 0 to n
	// rooms 0 ... n+1
	// rooms
	// 0    1    2    ...      n    n+1
	//   0|   1|   2|     n-1|   n|  
	// walls

	// for rooms 1 ... n, returns leftmost reachable room
	vector<vector<int> > keylocations(n+1);
	for(int i = 0; i <= n+1; i++){
		for(int a : keys[i]){
			keylocations[a].push_back(i);
		}
	}
	vector<int> prevkey(n+1);
	vector<int> nextkey(n+1);
	for(int i = 0; i <= n; i++){
		int type = walls[i];
		auto it = lower_bound(keylocations[type].begin(), keylocations[type].end(), i+1);
		nextkey[i] = *it;
		prevkey[i] = *(it-1);
	}

	// for each wall, find farthest one so that there's a conflict
	// then for a starting room, find dist to closest so that there is a conflict that extends past it
	vector<int> conflict(n+1, -1);
	for(int j = 0; j <= n; j++){
		for(int k = n; k >= j; k--){
			if(prevkey[k] <= j && nextkey[j] >= k+1){
				conflict[j] = k;
				break;
			}
		}
	}

	vector<int> ans(n+2, -1);
	for(int j = 1; j <= n; j++){
		for(int k = j-1; k >= 0; k--){
			if(conflict[k] >= j){
				ans[j] = j-1-k;
				break;
			}
		}
	}
	return ans;
}

int main(){
	cin.sync_with_stdio(0); cin.tie(0);
	int n;
	cin >> n;
	vector<int> walls; // what key need
	walls.push_back(0);
	for(int i = 1; i < n; i++){
		int c;
		cin >> c;
		walls.push_back(c);
	}
	walls.push_back(0);
	vector<vector<int> > keys(n+2);
	for(int i = 0; i <= n; i++){
		keys[0].push_back(i);
		keys[n+1].push_back(i);
	}
	for(int i = 1; i <= n; i++){
		int b;
		cin >> b;
		keys[i].resize(b);
		for(int j = 0; j < b; j++){
			cin >> keys[i][j];
		}
	}
	int q;
	cin >> q;
	vector<int> x(q);
	vector<int> y(q);
	for(int i = 0; i < q; i++){
		cin >> x[i] >> y[i];
	}

	vector<int> leftans = solve(n, walls, keys);
	reverse(walls.begin(), walls.end());
	reverse(keys.begin(), keys.end());
	vector<int> rightans = solve(n, walls, keys);
	reverse(rightans.begin(), rightans.end());
	for(int i = 0; i < q; i++){
		if(y[i]-x[i] <= rightans[x[i]] && y[i]-x[i] >= -leftans[x[i]]){
			cout << "YES" << '\n';
		} else {
			cout << "NO" << '\n';
		}
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 852 KB Output is correct
2 Correct 17 ms 1324 KB Output is correct
3 Correct 53 ms 1960 KB Output is correct
4 Correct 11 ms 1960 KB Output is correct
5 Correct 11 ms 1960 KB Output is correct
6 Correct 10 ms 1960 KB Output is correct
7 Correct 8 ms 1960 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 852 KB Output is correct
2 Correct 17 ms 1324 KB Output is correct
3 Correct 53 ms 1960 KB Output is correct
4 Correct 11 ms 1960 KB Output is correct
5 Correct 11 ms 1960 KB Output is correct
6 Correct 10 ms 1960 KB Output is correct
7 Correct 8 ms 1960 KB Output is correct
8 Correct 141 ms 11356 KB Output is correct
9 Correct 141 ms 15800 KB Output is correct
10 Correct 153 ms 20812 KB Output is correct
11 Correct 164 ms 25876 KB Output is correct
12 Correct 156 ms 28804 KB Output is correct
13 Correct 131 ms 33384 KB Output is correct
14 Correct 127 ms 37744 KB Output is correct
15 Correct 129 ms 42128 KB Output is correct
16 Correct 133 ms 46300 KB Output is correct
17 Correct 125 ms 50344 KB Output is correct
18 Correct 131 ms 54700 KB Output is correct
19 Correct 124 ms 59188 KB Output is correct
20 Correct 129 ms 63456 KB Output is correct
21 Correct 134 ms 67520 KB Output is correct
22 Correct 154 ms 71424 KB Output is correct
23 Correct 166 ms 75660 KB Output is correct
24 Correct 129 ms 79804 KB Output is correct
25 Correct 136 ms 84112 KB Output is correct
26 Correct 135 ms 88504 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3014 ms 113624 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 852 KB Output is correct
2 Correct 17 ms 1324 KB Output is correct
3 Correct 53 ms 1960 KB Output is correct
4 Correct 11 ms 1960 KB Output is correct
5 Correct 11 ms 1960 KB Output is correct
6 Correct 10 ms 1960 KB Output is correct
7 Correct 8 ms 1960 KB Output is correct
8 Correct 141 ms 11356 KB Output is correct
9 Correct 141 ms 15800 KB Output is correct
10 Correct 153 ms 20812 KB Output is correct
11 Correct 164 ms 25876 KB Output is correct
12 Correct 156 ms 28804 KB Output is correct
13 Correct 131 ms 33384 KB Output is correct
14 Correct 127 ms 37744 KB Output is correct
15 Correct 129 ms 42128 KB Output is correct
16 Correct 133 ms 46300 KB Output is correct
17 Correct 125 ms 50344 KB Output is correct
18 Correct 131 ms 54700 KB Output is correct
19 Correct 124 ms 59188 KB Output is correct
20 Correct 129 ms 63456 KB Output is correct
21 Correct 134 ms 67520 KB Output is correct
22 Correct 154 ms 71424 KB Output is correct
23 Correct 166 ms 75660 KB Output is correct
24 Correct 129 ms 79804 KB Output is correct
25 Correct 136 ms 84112 KB Output is correct
26 Correct 135 ms 88504 KB Output is correct
27 Execution timed out 3014 ms 113624 KB Time limit exceeded
28 Halted 0 ms 0 KB -