| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1109422 |
2024-11-06T16:20:03 Z |
sano |
Regions (IOI09_regions) |
C++14 |
|
85 ms |
26524 KB |
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#define ll long long
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define shit short double
#define pii pair<int, int>
#define NEK 2147483640
#define mod 1000000007
#define mod2 1000000009
#define rsz resize
#define prv1 43
#define prv2 47
#define D 8
using namespace std;
vec<vec<int>> g;
vec<int> eul1, eul2;
vec<vec<int>> odp;
vec<int> e;
vec<vec<int>> m;
int ti = 0;
void DFS(int x, int pr) {
eul1[x] = ti; ti++; m[e[x]].push_back(eul1[x]);
for (auto i : g[x]) {
if (i == pr) continue;
DFS(i, x);
}
eul2[x] = ti - 1;
return;
}
bool zorad(vec<int>& a, vec<int>& b) {
return a.size() > b.size();
}
void DFS2(int x, int pr, int k, int v = 0) {
if (e[x] == k) v++;
odp.back()[e[x]] += v;
for (auto i : g[x]) {
if (i == pr) continue;
DFS2(i, x, k, v);
}
return;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
//ifstream cin("promote.in");
//ofstream cout("promote.out");
int n, r, q;
cin >> n >> r >> q;
vec<vec<int>> reg(r);
g.resize(n); eul1.resize(n); eul2.resize(n);
e.resize(n);
cin >> e[0]; e[0]--;
reg[e[0]].push_back(0);
ffor(i, 1, n) {
int x; cin >> x; x--;
g[x].push_back(i);
g[i].push_back(x);
cin >> e[i]; e[i]--;
reg[e[i]].push_back(i);
}
m.resize(r);
DFS(0, -1);
return 0;
sort(reg.begin(), reg.end(), zorad);
vec<int> s_n(r);
For(i, reg.size()) {
if (reg[i].size() == 0) s_n[i] = -1;
s_n[e[reg[i][0]]] = i;
}
int odm = sqrt(n);
vec<int> trol(r, 0);
For(i, reg.size()) {
if (reg[i].size() >= odm) {
odp.push_back(trol);
DFS2(0, -1, e[reg[i][0]]);
}
}
For(i, m.size()) {
sort(m[i].begin(), m[i].end());
}
For(i, q) {
int r1, r2; cin >> r1 >> r2; r1--; r2--;
if (s_n[r1] >= odp.size()) {
int vys = 0;
for (auto i : reg[s_n[r1]]) {
int q1 = lower_bound(m[r2].begin(), m[r2].end(), eul1[i]) - m[r2].begin();
int q2 = upper_bound(m[r2].begin(), m[r2].end(), eul2[i]) - m[r2].begin();
vys += q2 - q1;
}
cout << vys << endl;
}
else {
cout << odp[s_n[r1]][r2] << endl;
}
}
return 0;
}
Compilation message
regions.cpp: In function 'int main()':
regions.cpp:99:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
99 | if (reg[i].size() >= odm) {
| ~~~~~~~~~~~~~~^~~~~~
regions.cpp:109:15: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | if (s_n[r1] >= odp.size()) {
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Unexpected end of file - int32 expected |
| 2 |
Incorrect |
1 ms |
336 KB |
Unexpected end of file - int32 expected |
| 3 |
Incorrect |
1 ms |
336 KB |
Unexpected end of file - int32 expected |
| 4 |
Incorrect |
1 ms |
336 KB |
Unexpected end of file - int32 expected |
| 5 |
Incorrect |
1 ms |
336 KB |
Unexpected end of file - int32 expected |
| 6 |
Incorrect |
1 ms |
504 KB |
Unexpected end of file - int32 expected |
| 7 |
Incorrect |
1 ms |
336 KB |
Unexpected end of file - int32 expected |
| 8 |
Incorrect |
1 ms |
592 KB |
Unexpected end of file - int32 expected |
| 9 |
Incorrect |
2 ms |
1104 KB |
Unexpected end of file - int32 expected |
| 10 |
Incorrect |
3 ms |
1104 KB |
Unexpected end of file - int32 expected |
| 11 |
Incorrect |
7 ms |
1616 KB |
Unexpected end of file - int32 expected |
| 12 |
Incorrect |
6 ms |
2128 KB |
Unexpected end of file - int32 expected |
| 13 |
Incorrect |
7 ms |
2384 KB |
Unexpected end of file - int32 expected |
| 14 |
Incorrect |
8 ms |
2896 KB |
Unexpected end of file - int32 expected |
| 15 |
Incorrect |
12 ms |
5456 KB |
Unexpected end of file - int32 expected |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
6736 KB |
Unexpected end of file - int32 expected |
| 2 |
Incorrect |
22 ms |
6736 KB |
Unexpected end of file - int32 expected |
| 3 |
Incorrect |
30 ms |
8776 KB |
Unexpected end of file - int32 expected |
| 4 |
Incorrect |
11 ms |
3152 KB |
Unexpected end of file - int32 expected |
| 5 |
Incorrect |
11 ms |
4688 KB |
Unexpected end of file - int32 expected |
| 6 |
Incorrect |
18 ms |
5200 KB |
Unexpected end of file - int32 expected |
| 7 |
Incorrect |
23 ms |
6800 KB |
Unexpected end of file - int32 expected |
| 8 |
Incorrect |
31 ms |
12104 KB |
Unexpected end of file - int32 expected |
| 9 |
Incorrect |
47 ms |
14408 KB |
Unexpected end of file - int32 expected |
| 10 |
Incorrect |
52 ms |
20016 KB |
Unexpected end of file - int32 expected |
| 11 |
Incorrect |
70 ms |
18504 KB |
Unexpected end of file - int32 expected |
| 12 |
Incorrect |
82 ms |
16204 KB |
Unexpected end of file - int32 expected |
| 13 |
Incorrect |
58 ms |
16968 KB |
Unexpected end of file - int32 expected |
| 14 |
Incorrect |
81 ms |
17736 KB |
Unexpected end of file - int32 expected |
| 15 |
Incorrect |
61 ms |
21444 KB |
Unexpected end of file - int32 expected |
| 16 |
Incorrect |
85 ms |
26524 KB |
Unexpected end of file - int32 expected |
| 17 |
Incorrect |
64 ms |
25100 KB |
Unexpected end of file - int32 expected |
