| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 944386 |
2024-03-12T16:25:31 Z |
FucKanh |
Regions (IOI09_regions) |
C++14 |
|
1754 ms |
43100 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;
in[h[u]].push_back(tin[u]);
out[h[u]].push_back(tout[u]);
}
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] >= 500) {
id[i] = ++dem;
c[i] = 0;
dfsc(1, i);
// cerr << i << ": " << endl;
// 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] >= 500) {
cout << cnt[id[r1]][r2] << endl;
}
else {
int pos = 1;
int ans = 0;
// cerr << r1 << ": ";
// for (int i = 1; i < in[r1].size(); i++) {
// cerr << in[r1][i] << " " << out[r1][i] << endl;
// }
// cerr << r2 << ": ";
// for (int i = 1; i < in[r2].size(); i++) {
// cerr << in[r2][i] << " " << out[r2][i] << endl;
// }
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:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for (int i = 0; i < a[u].size(); i++) {
| ~~^~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:89:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for (int i = 1; i < in[r1].size() && pos < in[r2].size(); i++) {
| ~~^~~~~~~~~~~~~~~
regions.cpp:89:54: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for (int i = 1; i < in[r1].size() && pos < in[r2].size(); i++) {
| ~~~~^~~~~~~~~~~~~~~
regions.cpp:90:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | while (pos < in[r2].size() && in[r2][pos] < in[r1][i]) pos++;
| ~~~~^~~~~~~~~~~~~~~
regions.cpp:91:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | 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 |
6 ms |
16984 KB |
Output isn't correct |
| 2 |
Incorrect |
4 ms |
16984 KB |
Output isn't correct |
| 3 |
Incorrect |
5 ms |
16984 KB |
Output isn't correct |
| 4 |
Incorrect |
6 ms |
16984 KB |
Output isn't correct |
| 5 |
Incorrect |
7 ms |
16984 KB |
Output isn't correct |
| 6 |
Incorrect |
12 ms |
17008 KB |
Output isn't correct |
| 7 |
Incorrect |
16 ms |
16984 KB |
Output isn't correct |
| 8 |
Incorrect |
16 ms |
16984 KB |
Output isn't correct |
| 9 |
Incorrect |
26 ms |
17496 KB |
Output isn't correct |
| 10 |
Incorrect |
45 ms |
17496 KB |
Output isn't correct |
| 11 |
Incorrect |
60 ms |
17496 KB |
Output isn't correct |
| 12 |
Incorrect |
59 ms |
18008 KB |
Output isn't correct |
| 13 |
Incorrect |
78 ms |
17752 KB |
Output isn't correct |
| 14 |
Incorrect |
118 ms |
18492 KB |
Output isn't correct |
| 15 |
Incorrect |
98 ms |
21336 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
665 ms |
21596 KB |
Output isn't correct |
| 2 |
Incorrect |
771 ms |
22048 KB |
Output isn't correct |
| 3 |
Incorrect |
1131 ms |
23912 KB |
Output isn't correct |
| 4 |
Incorrect |
116 ms |
18580 KB |
Output isn't correct |
| 5 |
Incorrect |
178 ms |
20568 KB |
Output isn't correct |
| 6 |
Incorrect |
415 ms |
22276 KB |
Output isn't correct |
| 7 |
Incorrect |
592 ms |
20764 KB |
Output isn't correct |
| 8 |
Incorrect |
620 ms |
27480 KB |
Output isn't correct |
| 9 |
Incorrect |
880 ms |
25956 KB |
Output isn't correct |
| 10 |
Incorrect |
1217 ms |
31620 KB |
Output isn't correct |
| 11 |
Incorrect |
1489 ms |
25396 KB |
Output isn't correct |
| 12 |
Incorrect |
814 ms |
26816 KB |
Output isn't correct |
| 13 |
Incorrect |
1012 ms |
27572 KB |
Output isn't correct |
| 14 |
Incorrect |
1344 ms |
29912 KB |
Output isn't correct |
| 15 |
Incorrect |
1481 ms |
33172 KB |
Output isn't correct |
| 16 |
Incorrect |
1754 ms |
42144 KB |
Output isn't correct |
| 17 |
Incorrect |
1625 ms |
43100 KB |
Output isn't correct |
