oj.uz

Submission #63047

# Submission time Handle Problem Language Result Execution time Memory
63047 2018-07-31T12:32:07 Z zadrga Long Mansion (JOI17_long_mansion) C++14
10 / 100
 3000 ms 68412 KB 
#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]);
			bool right = can(1, pos[i].se + 1, pos[i]);

			if(left)
				pos[i].fi--;

			//	pos[i] = merge(pos[i], pos[pos[i].fi - 1]);

			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:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:88: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:92:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &num);
   ~~~~~^~~~~~~~~~~~
long_mansion.cpp:94:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &x);
    ~~~~~^~~~~~~~~~
long_mansion.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:105: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

# Verdict Execution time Memory Grader output
1 Correct 21 ms 14200 KB Output is correct
2 Correct 28 ms 14408 KB Output is correct
3 Correct 57 ms 14564 KB Output is correct
4 Correct 21 ms 14564 KB Output is correct
5 Correct 26 ms 14804 KB Output is correct
6 Correct 21 ms 14804 KB Output is correct
7 Correct 24 ms 14828 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 14200 KB Output is correct
2 Correct 28 ms 14408 KB Output is correct
3 Correct 57 ms 14564 KB Output is correct
4 Correct 21 ms 14564 KB Output is correct
5 Correct 26 ms 14804 KB Output is correct
6 Correct 21 ms 14804 KB Output is correct
7 Correct 24 ms 14828 KB Output is correct
8 Correct 210 ms 20596 KB Output is correct
9 Correct 181 ms 25084 KB Output is correct
10 Correct 180 ms 29832 KB Output is correct
11 Correct 255 ms 34688 KB Output is correct
12 Correct 241 ms 38188 KB Output is correct
13 Correct 234 ms 42636 KB Output is correct
14 Correct 218 ms 47056 KB Output is correct
15 Correct 179 ms 51508 KB Output is correct
16 Correct 191 ms 55444 KB Output is correct
17 Correct 187 ms 59576 KB Output is correct
18 Correct 175 ms 62640 KB Output is correct
19 Correct 191 ms 62668 KB Output is correct
20 Correct 175 ms 62860 KB Output is correct
21 Correct 175 ms 63064 KB Output is correct
22 Correct 167 ms 63064 KB Output is correct
23 Correct 231 ms 63064 KB Output is correct
24 Correct 171 ms 63064 KB Output is correct
25 Correct 171 ms 63064 KB Output is correct
26 Correct 197 ms 63064 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2313 ms 68412 KB Output is correct
2 Execution timed out 3063 ms 68412 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 14200 KB Output is correct
2 Correct 28 ms 14408 KB Output is correct
3 Correct 57 ms 14564 KB Output is correct
4 Correct 21 ms 14564 KB Output is correct
5 Correct 26 ms 14804 KB Output is correct
6 Correct 21 ms 14804 KB Output is correct
7 Correct 24 ms 14828 KB Output is correct
8 Correct 210 ms 20596 KB Output is correct
9 Correct 181 ms 25084 KB Output is correct
10 Correct 180 ms 29832 KB Output is correct
11 Correct 255 ms 34688 KB Output is correct
12 Correct 241 ms 38188 KB Output is correct
13 Correct 234 ms 42636 KB Output is correct
14 Correct 218 ms 47056 KB Output is correct
15 Correct 179 ms 51508 KB Output is correct
16 Correct 191 ms 55444 KB Output is correct
17 Correct 187 ms 59576 KB Output is correct
18 Correct 175 ms 62640 KB Output is correct
19 Correct 191 ms 62668 KB Output is correct
20 Correct 175 ms 62860 KB Output is correct
21 Correct 175 ms 63064 KB Output is correct
22 Correct 167 ms 63064 KB Output is correct
23 Correct 231 ms 63064 KB Output is correct
24 Correct 171 ms 63064 KB Output is correct
25 Correct 171 ms 63064 KB Output is correct
26 Correct 197 ms 63064 KB Output is correct
27 Correct 2313 ms 68412 KB Output is correct
28 Execution timed out 3063 ms 68412 KB Time limit exceeded
29 Halted 0 ms 0 KB -