oj.uz

Submission #60384

# Submission time Handle Problem Language Result Execution time Memory
60384 2018-07-24T04:30:46 Z 김세빈(#1743) Long Mansion (JOI17_long_mansion) C++11
25 / 100
 804 ms 263168 KB 
#include <bits/stdc++.h>

using namespace std;

vector <int> K[505050];
int T[505050];
int L[505050], R[505050], X[505050], Y[505050];
bool C[505050];
int n;

void get_keys(int p) { for(int t: K[p]) C[t] = 1; }
void init_keys(int p) { for(int t: K[p]) C[t] = 0; }

void dnc(int s, int e)
{
	if(s == e){
		L[s] = R[s] = s;
		return;
	}
	
	int i, l, r, f, m = s + e >> 1;
	
	dnc(s, m); dnc(m + 1, e);
	
	for(i=l=r=m; i>=s; i--){
		get_keys(i);
		for(f=1; f; ){
			for(f=0; r<e && C[T[r]]; r++) get_keys(r + 1), f = 1;
			for(; l>s && C[T[l-1]]; l--) get_keys(l - 1), f = 1;
		}
		X[i] = l, Y[i] = r;
	}
	
	for(i=s; i<=m; i++){
		if(R[i] == m){
			R[i] = Y[L[i]];
			L[i] = X[L[i]];
		}
	}
	
	for(i=s; i<=e; i++) init_keys(i);
	
	for(i=l=r=m+1; i<=e; i++){
		get_keys(i);
		for(f=1; f; ){
			for(f=0; r<e && C[T[r]]; r++) get_keys(r + 1), f = 1;
			for(; l>s && C[T[l-1]]; l--) get_keys(l - 1), f = 1;
		}
		X[i] = l, Y[i] = r;
	}
	
	for(i=e; i>m; i--){
		if(L[i] == m + 1){
			L[i] = X[R[i]];
			R[i] = Y[R[i]];
		}
	}
	
	for(i=s; i<=e; i++) init_keys(i);
}

int main()
{
	int q, i, a, b;
	
	scanf("%d", &n);
	
	for(i=1; i<n; i++){
		scanf("%d", T+i);
	}
	
	for(i=1; i<=n; i++){
		scanf("%d", &a);
		for(; a--; ){
			scanf("%d", &b);
			K[i].push_back(b);
		}
	}
	
	dnc(1, n);
	
	scanf("%d", &q);
	
	for(; q--; ){
		scanf("%d%d", &a, &b);
		if(L[a] <= b && b <= R[a]) printf("YES\n");
		else printf("NO\n");
	}
	
	return 0;
}

Compilation message

long_mansion.cpp: In function 'void dnc(int, int)':
long_mansion.cpp:21:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int i, l, r, f, m = s + e >> 1;
                      ~~^~~
long_mansion.cpp: In function 'int main()':
long_mansion.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", T+i);
   ~~~~~^~~~~~~~~~~
long_mansion.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
   ~~~~~^~~~~~~~~~
long_mansion.cpp:75:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &b);
    ~~~~~^~~~~~~~~~
long_mansion.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 12408 KB Output is correct
2 Correct 18 ms 12596 KB Output is correct
3 Correct 19 ms 12788 KB Output is correct
4 Correct 24 ms 12992 KB Output is correct
5 Correct 20 ms 12992 KB Output is correct
6 Correct 19 ms 13032 KB Output is correct
7 Correct 17 ms 13084 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 12408 KB Output is correct
2 Correct 18 ms 12596 KB Output is correct
3 Correct 19 ms 12788 KB Output is correct
4 Correct 24 ms 12992 KB Output is correct
5 Correct 20 ms 12992 KB Output is correct
6 Correct 19 ms 13032 KB Output is correct
7 Correct 17 ms 13084 KB Output is correct
8 Correct 242 ms 18992 KB Output is correct
9 Correct 201 ms 23436 KB Output is correct
10 Correct 171 ms 28164 KB Output is correct
11 Correct 175 ms 33108 KB Output is correct
12 Correct 159 ms 36728 KB Output is correct
13 Correct 270 ms 41012 KB Output is correct
14 Correct 170 ms 45488 KB Output is correct
15 Correct 175 ms 49956 KB Output is correct
16 Correct 165 ms 53916 KB Output is correct
17 Correct 174 ms 58256 KB Output is correct
18 Correct 199 ms 62532 KB Output is correct
19 Correct 170 ms 66840 KB Output is correct
20 Correct 162 ms 71088 KB Output is correct
21 Correct 155 ms 75280 KB Output is correct
22 Correct 238 ms 79184 KB Output is correct
23 Correct 163 ms 83272 KB Output is correct
24 Correct 253 ms 87564 KB Output is correct
25 Correct 212 ms 91960 KB Output is correct
26 Correct 296 ms 96040 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 512 ms 109332 KB Output is correct
2 Correct 528 ms 116580 KB Output is correct
3 Correct 608 ms 123412 KB Output is correct
4 Correct 537 ms 130884 KB Output is correct
5 Correct 523 ms 138088 KB Output is correct
6 Correct 383 ms 144076 KB Output is correct
7 Correct 324 ms 150220 KB Output is correct
8 Correct 336 ms 156208 KB Output is correct
9 Correct 341 ms 162336 KB Output is correct
10 Correct 390 ms 168532 KB Output is correct
11 Correct 422 ms 174316 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 12408 KB Output is correct
2 Correct 18 ms 12596 KB Output is correct
3 Correct 19 ms 12788 KB Output is correct
4 Correct 24 ms 12992 KB Output is correct
5 Correct 20 ms 12992 KB Output is correct
6 Correct 19 ms 13032 KB Output is correct
7 Correct 17 ms 13084 KB Output is correct
8 Correct 242 ms 18992 KB Output is correct
9 Correct 201 ms 23436 KB Output is correct
10 Correct 171 ms 28164 KB Output is correct
11 Correct 175 ms 33108 KB Output is correct
12 Correct 159 ms 36728 KB Output is correct
13 Correct 270 ms 41012 KB Output is correct
14 Correct 170 ms 45488 KB Output is correct
15 Correct 175 ms 49956 KB Output is correct
16 Correct 165 ms 53916 KB Output is correct
17 Correct 174 ms 58256 KB Output is correct
18 Correct 199 ms 62532 KB Output is correct
19 Correct 170 ms 66840 KB Output is correct
20 Correct 162 ms 71088 KB Output is correct
21 Correct 155 ms 75280 KB Output is correct
22 Correct 238 ms 79184 KB Output is correct
23 Correct 163 ms 83272 KB Output is correct
24 Correct 253 ms 87564 KB Output is correct
25 Correct 212 ms 91960 KB Output is correct
26 Correct 296 ms 96040 KB Output is correct
27 Correct 512 ms 109332 KB Output is correct
28 Correct 528 ms 116580 KB Output is correct
29 Correct 608 ms 123412 KB Output is correct
30 Correct 537 ms 130884 KB Output is correct
31 Correct 523 ms 138088 KB Output is correct
32 Correct 383 ms 144076 KB Output is correct
33 Correct 324 ms 150220 KB Output is correct
34 Correct 336 ms 156208 KB Output is correct
35 Correct 341 ms 162336 KB Output is correct
36 Correct 390 ms 168532 KB Output is correct
37 Correct 422 ms 174316 KB Output is correct
38 Correct 733 ms 200968 KB Output is correct
39 Correct 631 ms 217524 KB Output is correct
40 Correct 742 ms 217960 KB Output is correct
41 Correct 804 ms 237832 KB Output is correct
42 Correct 413 ms 237832 KB Output is correct
43 Correct 376 ms 237832 KB Output is correct
44 Correct 552 ms 247612 KB Output is correct
45 Correct 576 ms 257924 KB Output is correct
46 Runtime error 579 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
47 Halted 0 ms 0 KB -