| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1112598 |
2024-11-14T11:39:41 Z |
FucKanh |
Regions (IOI09_regions) |
C++14 |
|
5191 ms |
66276 KB |
#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
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 |
| 1 |
Correct |
5 ms |
14928 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12880 KB |
Output is correct |
| 3 |
Correct |
6 ms |
12880 KB |
Output is correct |
| 4 |
Correct |
11 ms |
12880 KB |
Output is correct |
| 5 |
Correct |
14 ms |
12880 KB |
Output is correct |
| 6 |
Correct |
29 ms |
12880 KB |
Output is correct |
| 7 |
Correct |
47 ms |
12880 KB |
Output is correct |
| 8 |
Correct |
59 ms |
13064 KB |
Output is correct |
| 9 |
Correct |
90 ms |
13136 KB |
Output is correct |
| 10 |
Correct |
164 ms |
13392 KB |
Output is correct |
| 11 |
Correct |
210 ms |
13716 KB |
Output is correct |
| 12 |
Correct |
257 ms |
14120 KB |
Output is correct |
| 13 |
Correct |
304 ms |
13904 KB |
Output is correct |
| 14 |
Correct |
349 ms |
16464 KB |
Output is correct |
| 15 |
Correct |
440 ms |
18000 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1830 ms |
18932 KB |
Output is correct |
| 2 |
Correct |
2024 ms |
18116 KB |
Output is correct |
| 3 |
Correct |
3340 ms |
20304 KB |
Output is correct |
| 4 |
Correct |
518 ms |
14632 KB |
Output is correct |
| 5 |
Correct |
730 ms |
15756 KB |
Output is correct |
| 6 |
Correct |
1223 ms |
24504 KB |
Output is correct |
| 7 |
Correct |
1756 ms |
26780 KB |
Output is correct |
| 8 |
Correct |
1867 ms |
37772 KB |
Output is correct |
| 9 |
Correct |
3334 ms |
21320 KB |
Output is correct |
| 10 |
Correct |
3693 ms |
66276 KB |
Output is correct |
| 11 |
Correct |
5191 ms |
21852 KB |
Output is correct |
| 12 |
Correct |
1939 ms |
25532 KB |
Output is correct |
| 13 |
Correct |
2709 ms |
25480 KB |
Output is correct |
| 14 |
Correct |
3175 ms |
31972 KB |
Output is correct |
| 15 |
Correct |
4414 ms |
28656 KB |
Output is correct |
| 16 |
Correct |
4889 ms |
31556 KB |
Output is correct |
| 17 |
Correct |
4559 ms |
37252 KB |
Output is correct |
