| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1112124 |
2024-11-13T16:44:34 Z |
FucKanh |
Regions (IOI09_regions) |
C++14 |
|
2778 ms |
131072 KB |
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int maxn = 2e5 + 2;
const int maxr = 25001;
const int maxb = 450;
int tin[maxn], tout[maxn], pos[maxr];
int large[maxb][maxn],t;
bool control[maxb][maxn];
int compute[maxb][maxb];
vector<int> a[maxn], grp[maxr];
vector<int> pre;
void dfs(int u) {
tin[u] = ++t;
for (int v : a[u]) dfs(v);
tout[u] = t;
}
bool compare(const int &a, const int &b) {
return tin[a] < tin[b];
}
void solve() {
int n,r,q; cin >> n >> r >> q;
int block = sqrt(n) + 1;
int gt; cin >> gt;
grp[gt].push_back(1);
for (int i = 2; i <= n; i++) {
int x,y; cin >> x >> y;
a[x].push_back(i);
grp[y].push_back(i);
}
dfs(1);
for (int i = 1; i <= r; i++) {
sort(grp[i].begin(),grp[i].end(),compare);
if (grp[i].size() >= block) {
pre.push_back(i);
pos[i] = pre.size()-1;
}
}
for (int i = 0; i < pre.size(); i++) {
for (int v : grp[pre[i]]) {
large[i][tin[v]]=1;
for (int j = tout[v]; j >= tin[v]; j--) {
if (control[i][j]) break;
control[i][j] = 1;
}
}
for (int j = 1; j <= n; j++) large[i][j] += large[i][j-1];
for (int j = 0; j < pre.size(); j++) {
if (i != j) {
for (int v : grp[pre[j]]) {
compute[i][j]+=control[i][tin[v]];
}
}
}
}
for (int i = 1; i <= q; i++) {
int x,y; cin >> x >> y;
int ans = 0;
if (grp[x].size() >= block && grp[y].size() >= block) {
cout << compute[pos[x]][pos[y]] << endl;
}
else if (grp[x].size() < block && grp[y].size() < block) {
int p = 0;
for (int j = 0; j < grp[y].size(); j++) {
while (p < grp[x].size() && tout[grp[x][p]] < tin[grp[y][j]]) p++;
ans += tout[grp[x][p]] >= tin[grp[y][j]] && tin[grp[x][p]] <= tin[grp[y][j]];
}
cout << ans << endl;
}
else if (grp[x].size() < block && grp[y].size() >= block) {
vector<pii> v;
for (int val : grp[x]) {
if (v.empty() || v.back().second < tin[val]) v.push_back({tin[val], tout[val]});
else v.back().second = max(v.back().second,tout[val]);
}
for (pii val : v) {
ans += large[pos[y]][val.second] - large[pos[y]][val.first-1];
}
cout << ans << endl;
}
else {
for (int v : grp[y]) {
ans += control[pos[x]][tin[v]];
}
cout << ans << endl;
}
}
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
solve();
return 0;
}
Compilation message
regions.cpp: In function 'void solve()':
regions.cpp:42:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
42 | if (grp[i].size() >= block) {
| ~~~~~~~~~~~~~~^~~~~~~~
regions.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for (int i = 0; i < pre.size(); i++) {
| ~~^~~~~~~~~~~~
regions.cpp:57:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for (int j = 0; j < pre.size(); j++) {
| ~~^~~~~~~~~~~~
regions.cpp:69:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
69 | if (grp[x].size() >= block && grp[y].size() >= block) {
| ~~~~~~~~~~~~~~^~~~~~~~
regions.cpp:69:53: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
69 | if (grp[x].size() >= block && grp[y].size() >= block) {
| ~~~~~~~~~~~~~~^~~~~~~~
regions.cpp:72:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
72 | else if (grp[x].size() < block && grp[y].size() < block) {
| ~~~~~~~~~~~~~~^~~~~~~
regions.cpp:72:57: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
72 | else if (grp[x].size() < block && grp[y].size() < block) {
| ~~~~~~~~~~~~~~^~~~~~~
regions.cpp:74:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for (int j = 0; j < grp[y].size(); j++) {
| ~~^~~~~~~~~~~~~~~
regions.cpp:75:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | while (p < grp[x].size() && tout[grp[x][p]] < tin[grp[y][j]]) p++;
| ~~^~~~~~~~~~~~~~~
regions.cpp:80:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
80 | else if (grp[x].size() < block && grp[y].size() >= block) {
| ~~~~~~~~~~~~~~^~~~~~~
regions.cpp:80:57: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
80 | else if (grp[x].size() < block && grp[y].size() >= block) {
| ~~~~~~~~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
31 ms |
17488 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
37 ms |
17480 KB |
Execution killed with signal 11 |
| 3 |
Runtime error |
33 ms |
17488 KB |
Execution killed with signal 11 |
| 4 |
Incorrect |
9 ms |
8784 KB |
Output isn't correct |
| 5 |
Incorrect |
13 ms |
8784 KB |
Output isn't correct |
| 6 |
Runtime error |
34 ms |
17480 KB |
Execution killed with signal 11 |
| 7 |
Incorrect |
47 ms |
8784 KB |
Output isn't correct |
| 8 |
Incorrect |
51 ms |
8784 KB |
Output isn't correct |
| 9 |
Incorrect |
77 ms |
9040 KB |
Output isn't correct |
| 10 |
Incorrect |
131 ms |
9040 KB |
Output isn't correct |
| 11 |
Incorrect |
206 ms |
9296 KB |
Output isn't correct |
| 12 |
Incorrect |
219 ms |
9552 KB |
Output isn't correct |
| 13 |
Incorrect |
280 ms |
9296 KB |
Output isn't correct |
| 14 |
Incorrect |
307 ms |
11856 KB |
Output isn't correct |
| 15 |
Incorrect |
346 ms |
11392 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1614 ms |
32080 KB |
Output isn't correct |
| 2 |
Incorrect |
1897 ms |
22344 KB |
Output isn't correct |
| 3 |
Incorrect |
2778 ms |
22352 KB |
Output isn't correct |
| 4 |
Runtime error |
45 ms |
19544 KB |
Execution killed with signal 11 |
| 5 |
Runtime error |
42 ms |
21604 KB |
Execution killed with signal 11 |
| 6 |
Runtime error |
140 ms |
123800 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
265 ms |
109136 KB |
Execution killed with signal 11 |
| 8 |
Incorrect |
1794 ms |
102984 KB |
Output isn't correct |
| 9 |
Runtime error |
87 ms |
30536 KB |
Execution killed with signal 11 |
| 10 |
Runtime error |
277 ms |
131072 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
94 ms |
29140 KB |
Execution killed with signal 11 |
| 12 |
Runtime error |
138 ms |
38216 KB |
Execution killed with signal 11 |
| 13 |
Runtime error |
97 ms |
38028 KB |
Execution killed with signal 11 |
| 14 |
Runtime error |
164 ms |
78888 KB |
Execution killed with signal 11 |
| 15 |
Runtime error |
121 ms |
43328 KB |
Execution killed with signal 11 |
| 16 |
Runtime error |
547 ms |
49496 KB |
Execution killed with signal 11 |
| 17 |
Runtime error |
149 ms |
89928 KB |
Execution killed with signal 11 |
