General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
12863445 Practice:
nawa410
570D - 28 GNU C++11 Time limit exceeded on test 30 2000 ms 247164 KB 2015-09-06 11:45:24 2015-09-06 11:45:25
 
 
→ Source
#include <bits/stdc++.h>
#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
#define ll long long int
#define pb push_back
#define reset(a,b) memset(a,b,sizeof a)
#define _pause system("pause")
#define mp make_pair
#define fs first
#define sc second

using namespace std;

char _;
const int INF = (int)1e9;
const int MAX = 600000;
int N;
vector<int> v[MAX];
vector<int> h[MAX][30];
map<pair<int, int>, int> maps;
int in[MAX], out[MAX];
int cnt;
string str;

void dfs(int n, int d)
{
	h[d][str[n-1]-'a'].pb(cnt++);
	in[n] = cnt;
	for(int i=0;i<v[n].size();i++)
	{
		dfs(v[n][i], d+1);
	}
	out[n] = cnt++;
}

int main()
{
	int M;
	scan(N);
	scan(M);
	for(int i=2;i<=N;i++)
	{
		int n;scan(n);
		v[n].pb(i);
	}	
	cin>>str;
	cnt=0;
	dfs(1, 1);
	
	while(M--)
	{
		int V,H;scan(V);scan(H);
		int odd=0;
		if(maps[mp(V, H)]==1) {
			cout<<"Yes"<<endl;
			continue;
		}
		if(maps[mp(V, H)]==-1) {
			cout<<"No"<<endl;
			continue;
		}
		for(int i=0;i<26 && odd<2;i++)
		{
			if(h[H][i].size()==0) continue;

			int l=-1;
			int lo=0;
			int hi=h[H][i].size()-1;
			
			while(lo<=hi)
			{
				int m=(hi+lo)/2;
				if(in[V] <= h[H][i][m])
				{
					l = m;
					hi=m-1;
				}
				else
				{
					lo=m+1;
				}
			}
			if(l==-1) continue;
			int r=-1;
			lo=0;
			hi=h[H][i].size()-1;
			
			while(lo<=hi)
			{
				int m=(hi+lo)/2;
				if(out[V] >= h[H][i][m])
				{
					r = m;
					lo=m+1;
				}
				else
				{
					hi=m-1;
				}
			}
			if(r==-1) continue;
			int temp=r-l+1;
			if(temp%2!=0)odd++;
		}
		if(odd<2) {
			cout<<"Yes"<<endl;
			maps[mp(V, H)] = 1;
		}
		else {
			cout<<"No"<<endl;
			maps[mp(V, H)] = -1;
		}
	}

	return 0;
}


 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details