General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
12516572 Practice:
k0st1a
570D - 28 GNU C++11 Time limit exceeded on test 6 2000 ms 129356 KB 2015-08-13 22:05:41 2015-08-13 22:05:41
 
 
→ Source
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <sstream>
#include <map>
#include <set>
#include <numeric>
#include <memory.h>
#include <cstdio>
#include <assert.h>

using namespace std;

#define pb push_back
#define INF 1011111111
#define FOR(i, a, b) for (int _n(b), i(a); i < _n; i++)
#define rep(i, n) FOR(i, 0, n)
#define CL(a, v) memset((a), (v), sizeof(a))
#define mp make_pair
#define X first
#define Y second
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))

typedef long long ll;
typedef vector<int> VI;
typedef pair<int, int> pii;

/*** TEMPLATE CODE ENDS HERE */

const int N = 5e5 + 10;
VI g[N];
string s;
int tin[N], tout[N];
int len[N];

int* ch[N][26];
int* Dtin[N];
int* Dtout[N];

int dfs_len(int x, int h) {
  len[h]++;
  int d = 0;
  for (int to : g[x]) d = max(dfs_len(to, h + 1), d);
  return d + 1;
}

int last[N];
int D[N];

void dfs(int x, int h) {
  static int counter = -1;
  tin[x] = ++counter;
  D[x] = h;
  for (int to : g[x]) dfs(to, h + 1);
  tout[x] = counter;
  ch[h][s[x] - 'a'][last[h]] = 1;
  Dtin[h][last[h]] = tin[x];
  Dtout[h][last[h]] = tout[x];
  ++last[h];
}

int lower_bound(int* a, int n, int x) {
  int l = -1, r = n;
  while (r - l > 1) {
    int m = (l + r) / 2;
    if (a[m] >= x) {
      r = m;
    } else {
      l = m;
    }
  }
  return r;
}

int upper_bound(int* a, int n, int x) {
  int l = -1, r = n;
  while (r - l > 1) {
    int m = (l + r) / 2;
    if (a[m] > x) {
      r = m;
    } else {
      l = m;
    }
  }
  return r;
}

int main() {
#ifdef LOCAL_HOST
  freopen("input.txt", "r", stdin);
// freopen("output.txt","w",stdout);
#endif

  ios_base::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  FOR(i, 1, n) {
    int p;
    cin >> p;
    --p;
    g[p].pb(i);
  }
  cin >> s;

  int depth = dfs_len(0, 0) + 1;

  rep(i, depth) {
    Dtin[i] = new int[len[i]];
    Dtout[i] = new int[len[i]];
    rep(j, len[i]) {
      Dtin[i][j] = 0;
      Dtout[i][j] = 0;
    }
    rep(k, 26) {
      ch[i][k] = new int[len[i]];
      rep(j, len[i]) ch[i][k][j] = 0;
    }
  }

  dfs(0, 0);

  rep(i, n) rep(k, 26) { FOR(j, 1, len[i]) ch[i][k][j] += ch[i][k][j - 1]; }

  rep(i, m) {
    int v, h;
    cin >> v >> h;
    --v, --h;
    if (D[v] > h) {
      cout << "Yes\n";
      continue;
    }
    int from = lower_bound(Dtin[h], len[h], tin[v]);
    int end = upper_bound(Dtout[h], len[h], tout[v]) - 1;
    int odd = 0, even = 0;
    if (from <= end) {
      rep(k, 26) {
        int num = ch[h][k][end] - (from ? ch[h][k][from - 1] : 0);
        if (num & 1) {
          odd++;
        } else {
          even++;
        }
      }
      if (odd <= 1) {
        cout << "Yes\n";
      } else {
        cout << "No\n";
      }
    } else {
      cout << "Yes\n";
    }
  }

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