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
?
?
?
?