#include <bits/stdc++.h>
#define X first
#define Y second
typedef long long ll;
using namespace std;
const int MOD = 1e9 + 7;
const ll INF = 1e18;
int n, r, q, cv, q1, q2;
int sq;
vector<int> v[200002];
unordered_map<int, int> m[25002];
int w[200002];
int kol[200002];
int kol2[200002];
vector<int> g[200002];
int t;
int d1[200002];
int d2[200002];
stack<int> st;
void dfs(int x) {
for (int i = 0; i < v[x].size(); i ++) {
int sus = v[x][i];
dfs(sus);
kol[x] += kol[sus];
}
//cout << "mapa od " << x << ", " << t << " += " << kol[x] << endl;
m[w[x]][t] += kol[x];
}
void rek(int x, int y) {
y += kol2[x];
m[t][w[x]] += y;
for (int i = 0; i < v[x].size(); i ++) {
rek(v[x][i], y);
}
}
int tren;
void ord(int x) {
tren ++;
d1[x] = tren;
for (int i = 0; i < v[x].size(); i ++) {
ord(v[x][i]);
}
d2[x] = tren;
//cout << x << ": " << d1[x] << " " << d2[x] << endl;
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> r >> q;
sq = sqrt(n);
cin >> w[1];
g[w[1]].push_back(1);
for (int i = 2; i <= n; i ++) {
cin >> cv >> w[i];
g[w[i]].push_back(i);
v[cv].push_back(i);
}
ord(1);
for (int i = 1; i <= r; i ++) {
if (g[i].size() > sq) {
memset(kol, 0, sizeof kol);
memset(kol2, 0, sizeof kol2);
t = i;
for (int j = 0; j < g[i].size(); j ++) {
kol[g[i][j]] = 1;
kol2[g[i][j]] = 1;
}
dfs(1);
rek(1, 0);
}
}
for (int i = 0; i < q; i ++) {
cin >> q1 >> q2;
if (g[q1].size() <= sq && g[q2].size() <= sq) {
int p = 0;
int sol = 0;
for (int j = 0; j < g[q2].size(); j ++) {
while (st.size() > 0 && (d1[g[q2][j]] < d1[st.top()] || d2[st.top()] < d1[g[q2][j]])) st.pop();
while (p < g[q1].size() && d1[g[q1][p]] <= d1[g[q2][j]] && d1[g[q2][j]] <= d2[g[q1][p]]) {
st.push(g[q1][p]);
p ++;
}
sol += st.size();
}
while (st.size() > 0) st.pop();
cout << sol << endl;
}
else {
if (g[q1].size() > sq && g[q2].size() > sq) cout << m[q1][q2]/2 << endl;
else cout << m[q1][q2] << endl;
}
}
return 0;
}
Compilation message
regions.cpp: In function 'void dfs(int)':
regions.cpp:24:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v[x].size(); i ++) {
~~^~~~~~~~~~~~~
regions.cpp: In function 'void rek(int, int)':
regions.cpp:37:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v[x].size(); i ++) {
~~^~~~~~~~~~~~~
regions.cpp: In function 'void ord(int)':
regions.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v[x].size(); i ++) {
~~^~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:70:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (g[i].size() > sq) {
~~~~~~~~~~~~^~~~
regions.cpp:74:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < g[i].size(); j ++) {
~~^~~~~~~~~~~~~
regions.cpp:87:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (g[q1].size() <= sq && g[q2].size() <= sq) {
~~~~~~~~~~~~~^~~~~
regions.cpp:87:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (g[q1].size() <= sq && g[q2].size() <= sq) {
~~~~~~~~~~~~~^~~~~
regions.cpp:90:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < g[q2].size(); j ++) {
~~^~~~~~~~~~~~~~
regions.cpp:92:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (p < g[q1].size() && d1[g[q1][p]] <= d1[g[q2][j]] && d1[g[q2][j]] <= d2[g[q1][p]]) {
~~^~~~~~~~~~~~~~
regions.cpp:106:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (g[q1].size() > sq && g[q2].size() > sq) cout << m[q1][q2]/2 << endl;
~~~~~~~~~~~~~^~~~
regions.cpp:106:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (g[q1].size() > sq && g[q2].size() > sq) cout << m[q1][q2]/2 << endl;
~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
12664 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
11000 KB |
Output isn't correct |
| 3 |
Incorrect |
12 ms |
11128 KB |
Output isn't correct |
| 4 |
Incorrect |
17 ms |
11000 KB |
Output isn't correct |
| 5 |
Incorrect |
19 ms |
11128 KB |
Output isn't correct |
| 6 |
Correct |
32 ms |
11128 KB |
Output is correct |
| 7 |
Incorrect |
37 ms |
11128 KB |
Output isn't correct |
| 8 |
Incorrect |
31 ms |
11128 KB |
Output isn't correct |
| 9 |
Correct |
69 ms |
11512 KB |
Output is correct |
| 10 |
Incorrect |
68 ms |
11512 KB |
Output isn't correct |
| 11 |
Incorrect |
126 ms |
11768 KB |
Output isn't correct |
| 12 |
Incorrect |
167 ms |
12152 KB |
Output isn't correct |
| 13 |
Incorrect |
146 ms |
11896 KB |
Output isn't correct |
| 14 |
Incorrect |
222 ms |
14072 KB |
Output isn't correct |
| 15 |
Correct |
332 ms |
16504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1067 ms |
17260 KB |
Output isn't correct |
| 2 |
Incorrect |
1162 ms |
15828 KB |
Output isn't correct |
| 3 |
Incorrect |
1962 ms |
18808 KB |
Output isn't correct |
| 4 |
Incorrect |
236 ms |
12408 KB |
Output isn't correct |
| 5 |
Incorrect |
485 ms |
13688 KB |
Output isn't correct |
| 6 |
Incorrect |
1521 ms |
45072 KB |
Output isn't correct |
| 7 |
Incorrect |
2294 ms |
58900 KB |
Output isn't correct |
| 8 |
Incorrect |
3021 ms |
106680 KB |
Output isn't correct |
| 9 |
Incorrect |
1819 ms |
18936 KB |
Output isn't correct |
| 10 |
Runtime error |
2898 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 11 |
Incorrect |
2496 ms |
18632 KB |
Output isn't correct |
| 12 |
Incorrect |
1119 ms |
24832 KB |
Output isn't correct |
| 13 |
Incorrect |
1565 ms |
24952 KB |
Output isn't correct |
| 14 |
Incorrect |
3655 ms |
55284 KB |
Output isn't correct |
| 15 |
Incorrect |
2726 ms |
30408 KB |
Output isn't correct |
| 16 |
Incorrect |
2726 ms |
35976 KB |
Output isn't correct |
| 17 |
Incorrect |
3495 ms |
65668 KB |
Output isn't correct |
