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