| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 944371 |
2024-03-12T16:10:11 Z |
FucKanh |
Regions (IOI09_regions) |
C++14 |
|
1280 ms |
43244 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 = 25002;
int cnt[450][maxr], c[maxr], tin[maxn], tout[maxn], t, h[maxn], id[maxn], sz[maxr];
vector<int> a[maxn], in[maxn], out[maxn];
void dfs(int u, int pa = -1) {
tin[u] = ++t;
if (!c[h[u]]) c[h[u]] = u;
for (int i = 0; i < a[u].size(); i++) {
int v = a[u][i];
if (v == pa) continue;
dfs(v, u);
}
// cerr << "out " << u << " " << h[u] << " : " << c[h[u]] << endl;
tout[u] = t;
if (c[h[u]]==u) {
in[h[u]].push_back(tin[u]);
out[h[u]].push_back(tout[u]);
c[h[u]] = 0;
}
}
void dfsc(int u, int check, int pa = -1) {
if (h[u] == check && c[check] == 0) c[check] = u;
for (int i = 0; i < a[u].size(); i++) {
int v = a[u][i];
if (v == pa) continue;
dfsc(v, check, u);
}
if (c[check] == u) c[check] = 0;
if (c[check]) cnt[id[check]][h[u]]++;
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int n,r,q; cin >> n >> r >> q;
cin >> h[1];
for (int i = 2; i <= n; i++) {
int x; cin >> x >> h[i];
a[x].push_back(i);
sz[h[i]]++;
}
for (int i = 1; i <= r; i++) {
in[i].push_back(0);
out[i].push_back(0);
}
dfs(1);
// for (int i = 1; i <= r; i++) {
// cerr << i << ": " << endl;
// for (int j = 1; j < in[i].size(); j++) {
// cerr << in[i][j] << " " << out[i][j] << endl;
// }
// }
int dem = 0;
for (int i = 1; i <= r; i++) {
if (sz[i] * sz[i] >= n) {
id[i] = ++dem;
c[i] = 0;
dfsc(1, i);
// for (int j = 1; j <= r; j++) {
// cerr << cnt[dem][j] << " ";
// } cerr << endl;
}
}
for (int i =0; i < q; i++) {
int r1, r2; cin >> r1 >> r2;
if (sz[r1] * sz[r1] >= n) {
cout << cnt[id[r1]][r2] << "\n" << flush;
}
else {
int pos = 1;
int ans = 0;
for (int i = 1; i < in[r1].size() && pos < in[r2].size(); i++) {
while (pos < in[r2].size() && in[r2][pos] < in[r1][i]) pos++;
while (pos < in[r2].size() && in[r2][pos] >= in[r1][i] && out[r2][pos] <= out[r1][i]) ans++, pos++;
}
cout << ans << "\n" << flush;
}
}
return 0;
}
Compilation message
regions.cpp: In function 'void dfs(int, int)':
regions.cpp:16:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | for (int i = 0; i < a[u].size(); i++) {
| ~~^~~~~~~~~~~~~
regions.cpp: In function 'void dfsc(int, int, int)':
regions.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for (int i = 0; i < a[u].size(); i++) {
| ~~^~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:83:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for (int i = 1; i < in[r1].size() && pos < in[r2].size(); i++) {
| ~~^~~~~~~~~~~~~~~
regions.cpp:83:54: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for (int i = 1; i < in[r1].size() && pos < in[r2].size(); i++) {
| ~~~~^~~~~~~~~~~~~~~
regions.cpp:84:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | while (pos < in[r2].size() && in[r2][pos] < in[r1][i]) pos++;
| ~~~~^~~~~~~~~~~~~~~
regions.cpp:85:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | while (pos < in[r2].size() && in[r2][pos] >= in[r1][i] && out[r2][pos] <= out[r1][i]) ans++, pos++;
| ~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
16984 KB |
Output isn't correct |
| 2 |
Incorrect |
4 ms |
17040 KB |
Output isn't correct |
| 3 |
Incorrect |
4 ms |
16984 KB |
Output isn't correct |
| 4 |
Incorrect |
6 ms |
16984 KB |
Output isn't correct |
| 5 |
Incorrect |
7 ms |
17040 KB |
Output isn't correct |
| 6 |
Incorrect |
12 ms |
16984 KB |
Output isn't correct |
| 7 |
Incorrect |
14 ms |
16984 KB |
Output isn't correct |
| 8 |
Incorrect |
24 ms |
16984 KB |
Output isn't correct |
| 9 |
Incorrect |
26 ms |
17496 KB |
Output isn't correct |
| 10 |
Incorrect |
42 ms |
17240 KB |
Output isn't correct |
| 11 |
Incorrect |
55 ms |
17496 KB |
Output isn't correct |
| 12 |
Incorrect |
56 ms |
18008 KB |
Output isn't correct |
| 13 |
Incorrect |
87 ms |
18004 KB |
Output isn't correct |
| 14 |
Incorrect |
88 ms |
17936 KB |
Output isn't correct |
| 15 |
Incorrect |
79 ms |
21336 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
414 ms |
22776 KB |
Output isn't correct |
| 2 |
Incorrect |
538 ms |
20976 KB |
Output isn't correct |
| 3 |
Incorrect |
688 ms |
22928 KB |
Output isn't correct |
| 4 |
Incorrect |
144 ms |
18264 KB |
Output isn't correct |
| 5 |
Incorrect |
169 ms |
20076 KB |
Output isn't correct |
| 6 |
Incorrect |
405 ms |
25992 KB |
Output isn't correct |
| 7 |
Incorrect |
543 ms |
24912 KB |
Output isn't correct |
| 8 |
Incorrect |
566 ms |
37388 KB |
Output isn't correct |
| 9 |
Incorrect |
772 ms |
24384 KB |
Output isn't correct |
| 10 |
Incorrect |
1280 ms |
43244 KB |
Output isn't correct |
| 11 |
Incorrect |
1188 ms |
23496 KB |
Output isn't correct |
| 12 |
Incorrect |
534 ms |
25552 KB |
Output isn't correct |
| 13 |
Incorrect |
698 ms |
26488 KB |
Output isn't correct |
| 14 |
Incorrect |
960 ms |
28400 KB |
Output isn't correct |
| 15 |
Incorrect |
960 ms |
31348 KB |
Output isn't correct |
| 16 |
Incorrect |
1044 ms |
40672 KB |
Output isn't correct |
| 17 |
Incorrect |
1217 ms |
41296 KB |
Output isn't correct |
