This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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, ll> m[25002];
int w[200002];
int kol[200002];
int kol2[200002];
vector<int> g[200002];
int t;
int d1[200002];
int d2[200002];
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 loga[200002];
void update(int x, int y) {
for (x; x <= n; x += x & -x) loga[x] += y;
}
int query(int x) {
int out = 0;
for (x; x > 0; x -= x & -x) out += loga[x];
return out;
}
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) {
m[q1][q2] /= 2;
}
if (g[q1].size() <= sq && g[q2].size() <= sq && m[q1][q2] == 0) {
for (int j = 0; j < g[q2].size(); j ++) {
update(g[q2][j], 1);
}
for (int j = 0; j < g[q1].size(); j ++) {
m[q1][q2] += query(d2[ g[q1][j] ]);
m[q1][q2] -= query(d1[ g[q1][j] ]-1);
}
for (int j = 0; j < g[q2].size(); j ++) {
update(g[q2][j], -1);
}
if (m[q1][q2] == 0) m[q1][q2] = -1;
}
cout << max(0LL, m[q1][q2]) << endl;
}
return 0;
}
Compilation message (stderr)
regions.cpp: In function 'void dfs(int)':
regions.cpp:23: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:36: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:45: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 update(int, int)':
regions.cpp:55:8: warning: statement has no effect [-Wunused-value]
for (x; x <= n; x += x & -x) loga[x] += y;
^
regions.cpp: In function 'int query(int)':
regions.cpp:60:8: warning: statement has no effect [-Wunused-value]
for (x; x > 0; x -= x & -x) out += loga[x];
^
regions.cpp: In function 'int main()':
regions.cpp:81:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (g[i].size() > sq) {
~~~~~~~~~~~~^~~~
regions.cpp:85:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < g[i].size(); j ++) {
~~^~~~~~~~~~~~~
regions.cpp:97:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (g[q1].size() > sq && g[q2].size() > sq) {
~~~~~~~~~~~~~^~~~
regions.cpp:97:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (g[q1].size() > sq && g[q2].size() > sq) {
~~~~~~~~~~~~~^~~~
regions.cpp:101:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (g[q1].size() <= sq && g[q2].size() <= sq && m[q1][q2] == 0) {
~~~~~~~~~~~~~^~~~~
regions.cpp:101:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (g[q1].size() <= sq && g[q2].size() <= sq && m[q1][q2] == 0) {
~~~~~~~~~~~~~^~~~~
regions.cpp:102:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < g[q2].size(); j ++) {
~~^~~~~~~~~~~~~~
regions.cpp:106:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < g[q1].size(); j ++) {
~~^~~~~~~~~~~~~~
regions.cpp:111:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < g[q2].size(); j ++) {
~~^~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |