| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 944375 |
2024-03-12T16:16:53 Z |
FucKanh |
Regions (IOI09_regions) |
C++14 |
|
1229 ms |
42944 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;
}
}
cout << flush;
for (int i =0; i < q; i++) {
int r1, r2; cin >> r1 >> r2;
if (sz[r1] * sz[r1] >= n) {
cout << cnt[id[r1]][r2] << endl;
}
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 << endl;
}
}
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 |
16984 KB |
Output isn't correct |
| 3 |
Incorrect |
4 ms |
16984 KB |
Output isn't correct |
| 4 |
Incorrect |
9 ms |
17044 KB |
Output isn't correct |
| 5 |
Incorrect |
6 ms |
16984 KB |
Output isn't correct |
| 6 |
Incorrect |
11 ms |
16984 KB |
Output isn't correct |
| 7 |
Incorrect |
16 ms |
16980 KB |
Output isn't correct |
| 8 |
Incorrect |
23 ms |
16984 KB |
Output isn't correct |
| 9 |
Incorrect |
27 ms |
17496 KB |
Output isn't correct |
| 10 |
Incorrect |
36 ms |
17240 KB |
Output isn't correct |
| 11 |
Incorrect |
81 ms |
17496 KB |
Output isn't correct |
| 12 |
Incorrect |
59 ms |
17992 KB |
Output isn't correct |
| 13 |
Incorrect |
92 ms |
17752 KB |
Output isn't correct |
| 14 |
Incorrect |
93 ms |
18008 KB |
Output isn't correct |
| 15 |
Incorrect |
83 ms |
21336 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
433 ms |
22616 KB |
Output isn't correct |
| 2 |
Incorrect |
504 ms |
21196 KB |
Output isn't correct |
| 3 |
Incorrect |
755 ms |
23028 KB |
Output isn't correct |
| 4 |
Incorrect |
125 ms |
18264 KB |
Output isn't correct |
| 5 |
Incorrect |
171 ms |
20056 KB |
Output isn't correct |
| 6 |
Incorrect |
368 ms |
25964 KB |
Output isn't correct |
| 7 |
Incorrect |
555 ms |
25000 KB |
Output isn't correct |
| 8 |
Incorrect |
601 ms |
37520 KB |
Output isn't correct |
| 9 |
Incorrect |
747 ms |
24380 KB |
Output isn't correct |
| 10 |
Incorrect |
1229 ms |
42944 KB |
Output isn't correct |
| 11 |
Incorrect |
1116 ms |
23432 KB |
Output isn't correct |
| 12 |
Incorrect |
565 ms |
25856 KB |
Output isn't correct |
| 13 |
Incorrect |
603 ms |
26072 KB |
Output isn't correct |
| 14 |
Incorrect |
1006 ms |
28456 KB |
Output isn't correct |
| 15 |
Incorrect |
1042 ms |
31128 KB |
Output isn't correct |
| 16 |
Incorrect |
1122 ms |
40632 KB |
Output isn't correct |
| 17 |
Incorrect |
1127 ms |
41548 KB |
Output isn't correct |
