Submission #431235

#	Time	Username	Problem	Language	Result	Execution time	Memory
431235		jamezzz	Long Mansion (JOI17_long_mansion)	C++17	10 / 100	481 ms	42092 KiB

long_mansion

#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 (stderr)

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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 15
• Subtask 4: 0 / 75