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 ll long long
#define int ll
#define pii pair<int,int>
using namespace std;
const int maxn = 2e5 + 2;
int tin[maxn], tout[maxn],t,pos[maxn];
int control[maxn], num[maxn];
vector<int> re[maxn],a[maxn];
vector<int> small,big;
void dfs(int u) {
tin[u] = ++t;
for (int v : a[u]){
dfs(v);
}
tout[u] = t;
}
int compare(const int &a, const int &b) {
return tin[a] < tin[b];
}
void solve() {
int n,r,q; cin >> n >> r >> q;
int wat; cin >> wat;
re[wat].push_back(1);
int block = sqrt(n);
for (int i = 2; i <= n; i++) {
int x,y; cin >> x >> y;
a[x].push_back(i);
re[y].push_back(i);
}
dfs(1);
for (int i = 1; i <= r; i++) {
sort(re[i].begin(),re[i].end(),compare);
if (re[i].size() > block) {
big.push_back(i);
pos[i] = big.size();
}
else {
small.push_back(i);
pos[i] = -small.size();
}
}
// for (int i = 1; i <= r; i++) {
// cerr << "region "<< i << " pos " << pos[i] << " : ";
// for (int val : re[i]) cerr << val << " "; cerr << endl;
// }
vector<vector<int>> pre(big.size(), vector<int>(big.size(), 0));
vector<vector<int>> stob(small.size(), vector<int>(big.size(), 0));
vector<vector<int>> btos(big.size(), vector<int>(small.size(), 0));
for (int i = 0; i < big.size(); i++) {
memset(control,0,sizeof(control));
memset(num,0,sizeof(num));
for (int u : re[big[i]]) {
num[tin[u]]++;
control[tin[u]]++;
control[tout[u]+1]--;
}
for (int v = 1; v <= n; v++) {
num[v] += num[v-1];
control[v] += control[v-1];
}
for (int j = i+1; j < big.size(); j++) {
for (int u : re[big[j]]) {
pre[i][j] += control[tin[u]];
pre[j][i] += num[tout[u]] - num[tin[u]-1];
}
}
for (int j = 0; j < small.size(); j++) {
for (int u : re[small[j]]) {
btos[i][j] += control[tin[u]];
stob[j][i] += num[tout[u]] - num[tin[u]-1];
}
}
}
for (int i = 1; i <= q; i++) {
int x,y; cin >> x >> y;
if (pos[x] > 0 && pos[y] > 0) cout << pre[pos[x]-1][pos[y]-1] << endl;
else if (pos[x] > 0 && pos[y] < 0) cout << btos[pos[x]-1][-pos[y]-1] << endl;
else if (pos[x] < 0 && pos[y] > 0) cout << stob[-pos[x]-1][pos[y]-1] << endl;
else {
int l = 0;
int ans = 0;
stack<int> st;
// vector<int> p = &re[-pos[y]-1];
for (int u : re[y]) {
while (st.size() && !(tin[st.top()] <= tin[u] && tout[st.top()] >= tout[u])) st.pop();
while (l < re[x].size() && tin[re[x][l]] <= tin[u]) {
if (tin[re[x][l]] <= tin[u] && tout[re[x][l]] >= tout[u]) st.push(re[x][l]);
l++;
}
// if (i==2) cerr << u << " " << l << " " << st.size() << endl;
ans += st.size();
}
cout << ans << endl;
}
}
}
void file(string name) {
if (fopen((name + ".inp").c_str(), "r")) {
freopen((name + ".inp").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
}
signed main() {
file("REGIONS");
cin.tie(0) -> sync_with_stdio(0);
solve();
return 0;
}
Compilation message (stderr)
regions.cpp: In function 'void solve()':
regions.cpp:41:26: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
41 | if (re[i].size() > block) {
| ~~~~~~~~~~~~~^~~~~~~
regions.cpp:60:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for (int i = 0; i < big.size(); i++) {
| ~~^~~~~~~~~~~~
regions.cpp:72:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for (int j = i+1; j < big.size(); j++) {
| ~~^~~~~~~~~~~~
regions.cpp:78:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for (int j = 0; j < small.size(); j++) {
| ~~^~~~~~~~~~~~~~
regions.cpp:98:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | while (l < re[x].size() && tin[re[x][l]] <= tin[u]) {
| ~~^~~~~~~~~~~~~~
regions.cpp: In function 'void file(std::string)':
regions.cpp:111:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
111 | freopen((name + ".inp").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:112:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
112 | freopen((name + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |