oj.uz

Submission #63046

# Submission time Handle Problem Language Result Execution time Memory
63046 2018-07-31T12:28:25 Z zadrga Long Mansion (JOI17_long_mansion) C++14
0 / 100
 338 ms 21456 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] = 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:84:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:86: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:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &num);
   ~~~~~^~~~~~~~~~~~
long_mansion.cpp:92:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &x);
    ~~~~~^~~~~~~~~~
long_mansion.cpp:100:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:103: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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 14200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 14200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 338 ms 21456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 14200 KB Output isn't correct
2 Halted 0 ms 0 KB -