oj.uz

Submission #431235

# Submission time Handle Problem Language Result Execution time Memory
431235 2021-06-17T10:28:53 Z jamezzz Long Mansion (JOI17_long_mansion) C++17
10 / 100
 481 ms 42092 KB 
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#include <ext/rope>
using namespace __gnu_cxx;

typedef tree<long long, null_type, less<long long>,
rb_tree_tag, tree_order_statistics_node_update> pbds;
//less_equal for identical elements

#define DEBUG

#ifdef DEBUG
#define debug(...) printf(__VA_ARGS__);
#else
#define debug(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));

#define maxn 500005

int n,c[maxn],b[maxn],t,q,x,y;
bool have[maxn];
vector<int> a[maxn];
bool pos[5005][5005];

void small(){
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j)have[j]=false;
		for(int j=0;j<b[i];++j)have[a[i][j]]=true;
		int l=i,r=i;
		while(true){
			bool move=false;
			if(l>1&&have[c[l]]){
				--l;
				for(int j=0;j<b[l];++j){
					have[a[l][j]]=true;
				}
				move=true;
			}
			if(r<n&&have[c[r+1]]){
				++r;
				for(int j=0;j<b[r];++j){
					have[a[r][j]]=true;
				}
				move=true;
			}
			if(!move)break;
		}
		for(int j=l;j<=r;++j)pos[i][j]=true;
	}
	sf("%d",&q);
	for(int i=0;i<q;++i){
		sf("%d%d",&x,&y);
		if(pos[x][y])pf("YES\n");
		else pf("NO\n");
	}
}

int main(){
	sf("%d",&n);
	for(int i=2;i<=n;++i)sf("%d",&c[i]);
	for(int i=1;i<=n;++i){
		sf("%d",&b[i]);
		for(int j=0;j<b[i];++j){
			sf("%d",&t);
			a[i].pb(t);
		}
	}
	if(n<=5000)small();
}

Compilation message

long_mansion.cpp: In function 'void small()':
long_mansion.cpp:74:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |  sf("%d",&q);
      |    ^
long_mansion.cpp:76:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   sf("%d%d",&x,&y);
      |     ^
long_mansion.cpp: In function 'int main()':
long_mansion.cpp:83:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |  sf("%d",&n);
      |    ^
long_mansion.cpp:84:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |  for(int i=2;i<=n;++i)sf("%d",&c[i]);
      |                         ^
long_mansion.cpp:86:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |   sf("%d",&b[i]);
      |     ^
long_mansion.cpp:88:6: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |    sf("%d",&t);
      |      ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 20300 KB Output is correct
2 Correct 44 ms 25488 KB Output is correct
3 Correct 104 ms 35660 KB Output is correct
4 Correct 17 ms 20340 KB Output is correct
5 Correct 59 ms 21884 KB Output is correct
6 Correct 21 ms 20940 KB Output is correct
7 Correct 20 ms 20492 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 20300 KB Output is correct
2 Correct 44 ms 25488 KB Output is correct
3 Correct 104 ms 35660 KB Output is correct
4 Correct 17 ms 20340 KB Output is correct
5 Correct 59 ms 21884 KB Output is correct
6 Correct 21 ms 20940 KB Output is correct
7 Correct 20 ms 20492 KB Output is correct
8 Correct 182 ms 26196 KB Output is correct
9 Correct 192 ms 26052 KB Output is correct
10 Correct 225 ms 31616 KB Output is correct
11 Correct 292 ms 42092 KB Output is correct
12 Correct 162 ms 22048 KB Output is correct
13 Correct 154 ms 26308 KB Output is correct
14 Correct 150 ms 26280 KB Output is correct
15 Correct 180 ms 27020 KB Output is correct
16 Correct 481 ms 27792 KB Output is correct
17 Correct 425 ms 26320 KB Output is correct
18 Correct 154 ms 26308 KB Output is correct
19 Correct 168 ms 26468 KB Output is correct
20 Correct 217 ms 27552 KB Output is correct
21 Correct 198 ms 27820 KB Output is correct
22 Correct 209 ms 27420 KB Output is correct
23 Correct 177 ms 26380 KB Output is correct
24 Correct 184 ms 26388 KB Output is correct
25 Correct 188 ms 26380 KB Output is correct
26 Correct 188 ms 26180 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 20300 KB Output is correct
2 Correct 44 ms 25488 KB Output is correct
3 Correct 104 ms 35660 KB Output is correct
4 Correct 17 ms 20340 KB Output is correct
5 Correct 59 ms 21884 KB Output is correct
6 Correct 21 ms 20940 KB Output is correct
7 Correct 20 ms 20492 KB Output is correct
8 Correct 182 ms 26196 KB Output is correct
9 Correct 192 ms 26052 KB Output is correct
10 Correct 225 ms 31616 KB Output is correct
11 Correct 292 ms 42092 KB Output is correct
12 Correct 162 ms 22048 KB Output is correct
13 Correct 154 ms 26308 KB Output is correct
14 Correct 150 ms 26280 KB Output is correct
15 Correct 180 ms 27020 KB Output is correct
16 Correct 481 ms 27792 KB Output is correct
17 Correct 425 ms 26320 KB Output is correct
18 Correct 154 ms 26308 KB Output is correct
19 Correct 168 ms 26468 KB Output is correct
20 Correct 217 ms 27552 KB Output is correct
21 Correct 198 ms 27820 KB Output is correct
22 Correct 209 ms 27420 KB Output is correct
23 Correct 177 ms 26380 KB Output is correct
24 Correct 184 ms 26388 KB Output is correct
25 Correct 188 ms 26380 KB Output is correct
26 Correct 188 ms 26180 KB Output is correct
27 Incorrect 251 ms 18488 KB Output isn't correct
28 Halted 0 ms 0 KB -