oj.uz

Submission #125287

# Submission time Handle Problem Language Result Execution time Memory
125287 2019-07-05T04:47:06 Z 임유진(#3061) Long Mansion (JOI17_long_mansion) C++14
5 / 100
 87 ms 760 KB 
#include <stdio.h>
#include<vector>

using namespace std;

#define MAXN 5005
#define MAXQ 500005

vector<int> A[MAXN];
int B[MAXN], C[MAXN];
int X[MAXN], Y[MAXN];
int L[MAXN], R[MAXN];
bool key[MAXN];

int main() {
	int N, Q;

	scanf("%d", &N);
	for(int i = 0; i < N - 1; i++) scanf("%d", C + i);
	for(int i = 0; i < N; i++) {
		scanf("%d", B + i);
		int t;
		for(int j = 0; j < B[i]; j++) {
			scanf("%d", &t);
			A[i].push_back(t);
		}
	}
	scanf("%d", &Q);
	for(int i = 0; i < Q; i++) scanf("%d%d", X + i, Y + i);

	for(int i = 0; i < Q; i++) {
		X[i]--;
		Y[i]--;
	}

	for(int i = 0; i < N; i++) {
		L[i] = R[i] = i;
		for(int i = 0; i < N; i++) key[i] = false;
		for(auto a : A[i]) key[a] = true;
		while(true) {
			if(L[i] > 0 && key[C[L[i] - 1]]) {
				L[i]--;
				for(auto a : A[L[i]]) key[a] = true;
			}
			else if(R[i] < N - 1 && key[C[R[i]]]) {
				R[i]++;
				for(auto a : A[R[i]]) key[a] = true;
			}
			else break;
		}
	}

	//for(int i = 0; i < N; i++) printf("L = %d, R = %d\n", L[i], R[i]);

	for(int i = 0; i < Q; i++) {
		if(L[X[i]] <= Y[i] && Y[i] <= R[X[i]]) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

Compilation message

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:19:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < N - 1; i++) scanf("%d", C + i);
                                 ~~~~~^~~~~~~~~~~~~
long_mansion.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", B + i);
   ~~~~~^~~~~~~~~~~~~
long_mansion.cpp:24:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &t);
    ~~~~~^~~~~~~~~~
long_mansion.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:29:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < Q; i++) scanf("%d%d", X + i, Y + i);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 632 KB Output is correct
2 Correct 34 ms 632 KB Output is correct
3 Correct 87 ms 760 KB Output is correct
4 Correct 7 ms 632 KB Output is correct
5 Correct 45 ms 632 KB Output is correct
6 Correct 13 ms 604 KB Output is correct
7 Correct 11 ms 632 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 632 KB Output is correct
2 Correct 34 ms 632 KB Output is correct
3 Correct 87 ms 760 KB Output is correct
4 Correct 7 ms 632 KB Output is correct
5 Correct 45 ms 632 KB Output is correct
6 Correct 13 ms 604 KB Output is correct
7 Correct 11 ms 632 KB Output is correct
8 Execution timed out 13 ms 632 KB Time limit exceeded (wall clock)
9 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6 ms 504 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 632 KB Output is correct
2 Correct 34 ms 632 KB Output is correct
3 Correct 87 ms 760 KB Output is correct
4 Correct 7 ms 632 KB Output is correct
5 Correct 45 ms 632 KB Output is correct
6 Correct 13 ms 604 KB Output is correct
7 Correct 11 ms 632 KB Output is correct
8 Execution timed out 13 ms 632 KB Time limit exceeded (wall clock)
9 Halted 0 ms 0 KB -