답안 #63048 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
63048	2018-07-31T12:34:51 Z	zadrga	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	638 ms	204412 KB

long_mansion

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF ((int) 1e9)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 500111

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

vector<int> v[maxn];
pii pos[maxn];
int pov[maxn], l[maxn], d[maxn], cur[maxn];
int n;

bool can(int t, int ind, pii x){
	if(ind < 1 || ind > n)
		return 0;

	if(t == 0){
		if(x.fi <= d[ind] && d[ind] <= x.se)
			return 1;
		return 0;
	}

	if(t == 1){
		if(x.fi <= l[ind] && l[ind] <= x.se)
			return 1;
		return 0;
	}
}

pii merge(pii &a, pii &b){
	return mp(min(a.fi, b.fi), max(a.se, b.se));
}

void solve(){
	for(int i = 0; i < maxn; i++)
		cur[i] = -1;

	for(int i = 1; i < n; i++){
		for(int x : v[i])
			cur[x] = i;

		l[i + 1] = cur[pov[i]];
	}

	for(int i = 0; i < maxn; i++)
		cur[i] = 2 * maxn;

	for(int i = n; i > 1; i--){
		for(int x : v[i])
			cur[x] = i;

		d[i - 1] = cur[pov[i - 1]];
	}

	for(int i = 1; i <= n; i++){
		pos[i] = mp(i, i);
		bool ok = 1;

		while(ok){
			bool left = can(0, pos[i].fi - 1, pos[i]);
			if(left)
				pos[i] = merge(pos[i], pos[pos[i].fi - 1]);

			bool right = can(1, pos[i].se + 1, pos[i]);
			if(right)
				pos[i].se++;

			ok = max(left, right);
		}
	}
}

int main(){
	scanf("%d", &n);
	for(int i = 1; i < n; i++)
		scanf("%d", pov + i);

	for(int i = 1; i <= n; i++){
		int num, x;
		scanf("%d", &num);
		while(num--){
			scanf("%d", &x);
			v[i].pb(x);
		}
	}

	solve();

	int q;
	scanf("%d", &q);
	while(q--){
		int x, y;
		scanf("%d%d", &x, &y);
		if(pos[x].fi <= y && y <= pos[x].se)
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}

Compilation message

long_mansion.cpp: In function 'bool can(int, int, pii)':
long_mansion.cpp:37:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
long_mansion.cpp: In function 'int main()':
long_mansion.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", pov + i);
   ~~~~~^~~~~~~~~~~~~~~
long_mansion.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &num);
   ~~~~~^~~~~~~~~~~~
long_mansion.cpp:91:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &x);
    ~~~~~^~~~~~~~~~
long_mansion.cpp:99:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	14072 KB	Output is correct
2	Correct	17 ms	14180 KB	Output is correct
3	Correct	25 ms	14488 KB	Output is correct
4	Correct	25 ms	14488 KB	Output is correct
5	Correct	22 ms	14488 KB	Output is correct
6	Correct	23 ms	14488 KB	Output is correct
7	Correct	17 ms	14508 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	14072 KB	Output is correct
2	Correct	17 ms	14180 KB	Output is correct
3	Correct	25 ms	14488 KB	Output is correct
4	Correct	25 ms	14488 KB	Output is correct
5	Correct	22 ms	14488 KB	Output is correct
6	Correct	23 ms	14488 KB	Output is correct
7	Correct	17 ms	14508 KB	Output is correct
8	Correct	201 ms	16012 KB	Output is correct
9	Correct	227 ms	16012 KB	Output is correct
10	Correct	204 ms	16076 KB	Output is correct
11	Correct	237 ms	16332 KB	Output is correct
12	Correct	204 ms	16332 KB	Output is correct
13	Correct	201 ms	16332 KB	Output is correct
14	Correct	175 ms	16332 KB	Output is correct
15	Correct	195 ms	16332 KB	Output is correct
16	Correct	178 ms	16352 KB	Output is correct
17	Correct	187 ms	16352 KB	Output is correct
18	Correct	213 ms	16352 KB	Output is correct
19	Correct	212 ms	16352 KB	Output is correct
20	Correct	218 ms	16352 KB	Output is correct
21	Correct	215 ms	16428 KB	Output is correct
22	Correct	265 ms	16428 KB	Output is correct
23	Correct	233 ms	16428 KB	Output is correct
24	Correct	186 ms	16428 KB	Output is correct
25	Correct	209 ms	16428 KB	Output is correct
26	Correct	180 ms	16428 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	358 ms	21644 KB	Output is correct
2	Correct	393 ms	21676 KB	Output is correct
3	Correct	390 ms	21676 KB	Output is correct
4	Correct	425 ms	21704 KB	Output is correct
5	Correct	343 ms	21704 KB	Output is correct
6	Correct	303 ms	21704 KB	Output is correct
7	Correct	323 ms	21704 KB	Output is correct
8	Correct	264 ms	21704 KB	Output is correct
9	Correct	238 ms	21704 KB	Output is correct
10	Correct	270 ms	21704 KB	Output is correct
11	Correct	248 ms	21704 KB	Output is correct

Subtask #4
75.0 / 75.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	14072 KB	Output is correct
2	Correct	17 ms	14180 KB	Output is correct
3	Correct	25 ms	14488 KB	Output is correct
4	Correct	25 ms	14488 KB	Output is correct
5	Correct	22 ms	14488 KB	Output is correct
6	Correct	23 ms	14488 KB	Output is correct
7	Correct	17 ms	14508 KB	Output is correct
8	Correct	201 ms	16012 KB	Output is correct
9	Correct	227 ms	16012 KB	Output is correct
10	Correct	204 ms	16076 KB	Output is correct
11	Correct	237 ms	16332 KB	Output is correct
12	Correct	204 ms	16332 KB	Output is correct
13	Correct	201 ms	16332 KB	Output is correct
14	Correct	175 ms	16332 KB	Output is correct
15	Correct	195 ms	16332 KB	Output is correct
16	Correct	178 ms	16352 KB	Output is correct
17	Correct	187 ms	16352 KB	Output is correct
18	Correct	213 ms	16352 KB	Output is correct
19	Correct	212 ms	16352 KB	Output is correct
20	Correct	218 ms	16352 KB	Output is correct
21	Correct	215 ms	16428 KB	Output is correct
22	Correct	265 ms	16428 KB	Output is correct
23	Correct	233 ms	16428 KB	Output is correct
24	Correct	186 ms	16428 KB	Output is correct
25	Correct	209 ms	16428 KB	Output is correct
26	Correct	180 ms	16428 KB	Output is correct
27	Correct	358 ms	21644 KB	Output is correct
28	Correct	393 ms	21676 KB	Output is correct
29	Correct	390 ms	21676 KB	Output is correct
30	Correct	425 ms	21704 KB	Output is correct
31	Correct	343 ms	21704 KB	Output is correct
32	Correct	303 ms	21704 KB	Output is correct
33	Correct	323 ms	21704 KB	Output is correct
34	Correct	264 ms	21704 KB	Output is correct
35	Correct	238 ms	21704 KB	Output is correct
36	Correct	270 ms	21704 KB	Output is correct
37	Correct	248 ms	21704 KB	Output is correct
38	Correct	638 ms	45800 KB	Output is correct
39	Correct	493 ms	62208 KB	Output is correct
40	Correct	445 ms	62760 KB	Output is correct
41	Correct	514 ms	82788 KB	Output is correct
42	Correct	315 ms	82788 KB	Output is correct
43	Correct	373 ms	82788 KB	Output is correct
44	Correct	455 ms	92340 KB	Output is correct
45	Correct	559 ms	102648 KB	Output is correct
46	Correct	398 ms	112996 KB	Output is correct
47	Correct	340 ms	115424 KB	Output is correct
48	Correct	278 ms	122512 KB	Output is correct
49	Correct	388 ms	137752 KB	Output is correct
50	Correct	444 ms	147836 KB	Output is correct
51	Correct	465 ms	158336 KB	Output is correct
52	Correct	434 ms	167336 KB	Output is correct
53	Correct	449 ms	182792 KB	Output is correct
54	Correct	601 ms	199024 KB	Output is correct
55	Correct	509 ms	204412 KB	Output is correct

답안 #63048

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 5.0 / 5.0

Subtask #3 15.0 / 15.0

Subtask #4 75.0 / 75.0

Subtask #1
5.0 / 5.0

Subtask #2
5.0 / 5.0

Subtask #3
15.0 / 15.0

Subtask #4
75.0 / 75.0