QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#167159#366. Long Distance CoachCrysfly0 4ms19812kbC++171.6kb2023-09-07 11:02:302023-09-07 11:02:49

Judging History

你现在查看的是最新测评结果

  • [2023-09-07 11:02:49]
  • 评测
  • 测评结果:0
  • 用时:4ms
  • 内存:19812kb
  • [2023-09-07 11:02:30]
  • 提交

answer

#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
//#define int long long
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 500005
#define inf 0x3f3f3f3f

int n,m,c[maxn],pos[maxn];
vi a[maxn];
int L[maxn],R[maxn],tol[maxn],tor[maxn];
bool vis[maxn];
void dfs(int x)
{
	if(vis[x])return; vis[x]=1;
	L[x]=R[x]=x;
    int ok=1;
    while(ok){
        ok=0;
        int tl=L[x]-1,tr=R[x]+1;
        if(tor[tl] && tor[tl]<tr){
            dfs(tl);
            if (L[tl]<L[x])
                L[x]=L[tl],ok=1;
            if (R[tl]>R[x])
                R[x]=R[tl],ok=1;
        }
        if(tol[tr] && tol[tr]>tl){
            dfs(tr);
            if (L[tr]<L[x])
                L[x]=L[tr],ok=1;
            if (R[tr]>R[x])
                R[x]=R[tr],ok=1;
        }
    }
}
signed main()
{
	n=read();
	For(i,1,n-1)c[i]=read();
	For(i,1,n){
		int sz=read(); a[i].resize(sz);
		For(j,0,sz-1) a[i][j]=read();
	}
	Rep(i,n,2){
		for(auto t:a[i]) pos[t]=i;
		tor[i-1]=pos[c[i-1]];
	}
	memset(pos,0,sizeof pos);
	For(i,1,n-1){
		for(auto t:a[i]) pos[t]=i;
		tol[i+1]=pos[c[i]];
	}
	For(i,1,n)dfs(i);
	int Q=read();
	while(Q--){
		int x=read(),y=read();
		if(L[x]<=y&&R[x]>=y)puts("YES");
		else puts("NO");
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 19812kb

input:

999999999999 1 1 1000000 4
1
2 3

output:

NO

result:

wrong answer 1st lines differ - expected: '499999999999000003', found: 'NO'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%