답안 #69421 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69421	2018-08-20T20:03:09 Z	TadijaSebez	Long Mansion (JOI17_long_mansion)	C++11	25 / 100	269 ms	192200 KB

long_mansion

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
const int N=200050;
int pos[N],lo[N],hi[N],c[N],l[N],r[N];
vector<int> a[N];
bool on(int l, int r, int x){ return l<=x && r>=x;}
bool can(int l, int r, int x){ return (lo[x] && on(l,r,lo[x])) || (hi[x] && on(l,r,hi[x]));}
int main()
{
	int n,q,i,j,x,y;
	scanf("%i",&n);
	for(i=1;i<n;i++) scanf("%i",&c[i]);
	for(i=1;i<=n;i++)
	{
		scanf("%i",&x);
		a[i].resize(x);
		for(j=0;j<x;j++) scanf("%i",&a[i][j]);
	}
	for(i=1;i<=n;i++) pos[i]=0;
	for(i=n;i>1;i--)
	{
		for(j=0;j<a[i].size();j++) pos[a[i][j]]=i;
		hi[i-1]=pos[c[i-1]];
	}
	for(i=1;i<=n;i++) pos[i]=0;
	for(i=1;i<n;i++)
	{
		for(j=0;j<a[i].size();j++) pos[a[i][j]]=i;
		lo[i]=pos[c[i]];
	}
	//for(i=1;i<n;i++) printf("->%i:%i %i\n",i,lo[i],hi[i]);
	for(i=1;i<=n;i++)
	{
		l[i]=r[i]=i;
		while(1)
		{
			if(l[i]>1 && can(l[i],r[i],l[i]-1))
			{
				//printf("%i %i\n",l[l[i]-1],r[l[i]-1]);
				r[i]=max(r[i],r[l[i]-1]);
				l[i]=l[l[i]-1];
			}
			else if(r[i]<n && can(l[i],r[i],r[i])) r[i]++;
			else break;
		}
		//printf("%i:%i %i\n",i,l[i],r[i]);
	}
	scanf("%i",&q);
	while(q--)
	{
		scanf("%i %i",&x,&y);
		if(on(l[x],r[x],y)) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

Compilation message

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:25:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<a[i].size();j++) pos[a[i][j]]=i;
           ~^~~~~~~~~~~~
long_mansion.cpp:31:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<a[i].size();j++) pos[a[i][j]]=i;
           ~^~~~~~~~~~~~
long_mansion.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
long_mansion.cpp:15:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1;i<n;i++) scanf("%i",&c[i]);
                   ~~~~~^~~~~~~~~~~~
long_mansion.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i",&x);
   ~~~~~^~~~~~~~~
long_mansion.cpp:20:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(j=0;j<x;j++) scanf("%i",&a[i][j]);
                    ~~~~~^~~~~~~~~~~~~~~
long_mansion.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&q);
  ~~~~~^~~~~~~~~
long_mansion.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	5240 KB	Output is correct
2	Correct	11 ms	5556 KB	Output is correct
3	Correct	13 ms	5764 KB	Output is correct
4	Correct	10 ms	5764 KB	Output is correct
5	Correct	8 ms	5764 KB	Output is correct
6	Correct	10 ms	5888 KB	Output is correct
7	Correct	11 ms	5964 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	5240 KB	Output is correct
2	Correct	11 ms	5556 KB	Output is correct
3	Correct	13 ms	5764 KB	Output is correct
4	Correct	10 ms	5764 KB	Output is correct
5	Correct	8 ms	5764 KB	Output is correct
6	Correct	10 ms	5888 KB	Output is correct
7	Correct	11 ms	5964 KB	Output is correct
8	Correct	149 ms	12084 KB	Output is correct
9	Correct	153 ms	16252 KB	Output is correct
10	Correct	159 ms	20996 KB	Output is correct
11	Correct	159 ms	26052 KB	Output is correct
12	Correct	147 ms	29416 KB	Output is correct
13	Correct	149 ms	33944 KB	Output is correct
14	Correct	143 ms	38320 KB	Output is correct
15	Correct	143 ms	42708 KB	Output is correct
16	Correct	144 ms	46748 KB	Output is correct
17	Correct	158 ms	50920 KB	Output is correct
18	Correct	145 ms	55292 KB	Output is correct
19	Correct	142 ms	59672 KB	Output is correct
20	Correct	146 ms	64048 KB	Output is correct
21	Correct	135 ms	67984 KB	Output is correct
22	Correct	146 ms	72144 KB	Output is correct
23	Correct	151 ms	76164 KB	Output is correct
24	Correct	143 ms	80400 KB	Output is correct
25	Correct	145 ms	84628 KB	Output is correct
26	Correct	145 ms	89120 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	254 ms	101892 KB	Output is correct
2	Correct	250 ms	109072 KB	Output is correct
3	Correct	260 ms	116144 KB	Output is correct
4	Correct	258 ms	123448 KB	Output is correct
5	Correct	269 ms	130568 KB	Output is correct
6	Correct	223 ms	137212 KB	Output is correct
7	Correct	209 ms	143328 KB	Output is correct
8	Correct	210 ms	149440 KB	Output is correct
9	Correct	230 ms	155484 KB	Output is correct
10	Correct	225 ms	161496 KB	Output is correct
11	Correct	249 ms	167520 KB	Output is correct

Subtask #4
0 / 75.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	5240 KB	Output is correct
2	Correct	11 ms	5556 KB	Output is correct
3	Correct	13 ms	5764 KB	Output is correct
4	Correct	10 ms	5764 KB	Output is correct
5	Correct	8 ms	5764 KB	Output is correct
6	Correct	10 ms	5888 KB	Output is correct
7	Correct	11 ms	5964 KB	Output is correct
8	Correct	149 ms	12084 KB	Output is correct
9	Correct	153 ms	16252 KB	Output is correct
10	Correct	159 ms	20996 KB	Output is correct
11	Correct	159 ms	26052 KB	Output is correct
12	Correct	147 ms	29416 KB	Output is correct
13	Correct	149 ms	33944 KB	Output is correct
14	Correct	143 ms	38320 KB	Output is correct
15	Correct	143 ms	42708 KB	Output is correct
16	Correct	144 ms	46748 KB	Output is correct
17	Correct	158 ms	50920 KB	Output is correct
18	Correct	145 ms	55292 KB	Output is correct
19	Correct	142 ms	59672 KB	Output is correct
20	Correct	146 ms	64048 KB	Output is correct
21	Correct	135 ms	67984 KB	Output is correct
22	Correct	146 ms	72144 KB	Output is correct
23	Correct	151 ms	76164 KB	Output is correct
24	Correct	143 ms	80400 KB	Output is correct
25	Correct	145 ms	84628 KB	Output is correct
26	Correct	145 ms	89120 KB	Output is correct
27	Correct	254 ms	101892 KB	Output is correct
28	Correct	250 ms	109072 KB	Output is correct
29	Correct	260 ms	116144 KB	Output is correct
30	Correct	258 ms	123448 KB	Output is correct
31	Correct	269 ms	130568 KB	Output is correct
32	Correct	223 ms	137212 KB	Output is correct
33	Correct	209 ms	143328 KB	Output is correct
34	Correct	210 ms	149440 KB	Output is correct
35	Correct	230 ms	155484 KB	Output is correct
36	Correct	225 ms	161496 KB	Output is correct
37	Correct	249 ms	167520 KB	Output is correct
38	Runtime error	179 ms	192200 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
39	Halted	0 ms	0 KB	-

답안 #69421

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 5.0 / 5.0

Subtask #3 15.0 / 15.0

Subtask #4 0 / 75.0

Subtask #1
5.0 / 5.0

Subtask #2
5.0 / 5.0

Subtask #3
15.0 / 15.0

Subtask #4
0 / 75.0