| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 657212 |
2022-11-09T08:17:40 Z |
rafatoa |
Regions (IOI09_regions) |
C++17 |
|
3883 ms |
72652 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#pragma GCC optimize ("Ofast")
#define double ld
#define F first
#define S second
#define vi vector<int>
#define vvi vector<vi>
#define pi pair<int, int>
#define vpi vector<pi>
#define vb vector<bool>
#define vvb vector<vb>
#define pb push_back
#define ppb pop_back
#define read(a) for(auto &x:a) cin >> x;
#define print(a) for(auto x:a) cout << x << " "; cout << "\n";
#define rs resize
#define as assign
#define vc vector<char>
#define vvc vector<vc>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define MP make_pair
#define int long long
const int inf = 2e9;
const int INF = 4e18;
void solve(){
int n, r, q; cin >> n >> r >> q;
vvi adj(n+1), R(r+1);
vi h(n+1);
cin >> h[1];
for(int i=2; i<=n; i++){
int p; cin >> p;
adj[p].pb(i);
cin >> h[i];
}
vector<vpi> ac(r+1);
vi in(n+1), sub(n+1);
int time = 0;
function<void(int)> dfs = [&](int s){
R[h[s]].pb(s);
in[s] = time++;
sub[s] = 1;
for(auto u:adj[s]){
dfs(u);
sub[s] += sub[u];
}
ac[h[s]].pb({in[s], 1}); ac[h[s]].pb({in[s]+sub[s], -1});
};
dfs(1);
int sq = sqrt(n);
for(int i=1; i<=r; i++)
sort(all(ac[i]));
vvi ans(r+1), ans2(r+1);
for(int r1=1; r1<=r; r1++){
if(R[r1].size() <= sq) continue;
ans[r1] = ans2[r1] = vi(r+1, 0);
//for(int r2=1; r2<=r; r2++){
// if(r1 == r2) continue;
// int ix = 0, sum = ac[r2][ix].S;
// for(int i=0; i<R[r1].size(); i++){
// while(ix+1 < ac[r2].size() && ac[r2][ix+1].F <= in[R[r1][i]]) sum += ac[r2][++ix].S;
// if(ac[r2][ix].F > in[R[r1][i]]) continue;
// ans[r1][r2] += sum;
// }
//}
}
for(int r1=1; r1<=r; r1++){
if(R[r1].size() <= sq) continue;
function<void(int, int)> dfs2 = [&](int s, int cnt){
if(h[s] == r1) cnt++;
else if(cnt > 0) ans2[r1][h[s]] += cnt;
for(auto u:adj[s])
dfs2(u, cnt);
};
dfs2(1, 0);
}
while(q--){
int r1, r2; cin >> r1 >> r2;
//if(R[r2].size() > sq) cout << ans[r2][r1] << endl;
if(R[r1].size() > sq) cout << ans2[r1][r2] << endl;
else {
if(ac[r1].empty()){
cout << 0 << endl;
continue;
}
int aux = 0, ix = 0, sum = ac[r1][ix].S;
for(int i=0; i<R[r2].size(); i++){
while(ix+1 < ac[r1].size() && ac[r1][ix+1].F <= in[R[r2][i]]) sum += ac[r1][++ix].S;
if(ac[r1][ix].F > in[R[r2][i]]) continue;
aux += sum;
}
cout << aux << endl;
}
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
// #ifndef ONLINE_JUDGE
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// #endif
solve();
return 0;
}
Compilation message
regions.cpp: In function 'void solve()':
regions.cpp:67:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
67 | if(R[r1].size() <= sq) continue;
| ~~~~~~~~~~~~~^~~~~
regions.cpp:82:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
82 | if(R[r1].size() <= sq) continue;
| ~~~~~~~~~~~~~^~~~~
regions.cpp:96:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
96 | if(R[r1].size() > sq) cout << ans2[r1][r2] << endl;
| ~~~~~~~~~~~~~^~~~
regions.cpp:103:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for(int i=0; i<R[r2].size(); i++){
| ~^~~~~~~~~~~~~
regions.cpp:104:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | while(ix+1 < ac[r1].size() && ac[r1][ix+1].F <= in[R[r2][i]]) sum += ac[r1][++ix].S;
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Correct |
1 ms |
208 KB |
Output is correct |
| 3 |
Correct |
2 ms |
208 KB |
Output is correct |
| 4 |
Correct |
4 ms |
208 KB |
Output is correct |
| 5 |
Correct |
5 ms |
336 KB |
Output is correct |
| 6 |
Correct |
17 ms |
464 KB |
Output is correct |
| 7 |
Correct |
23 ms |
464 KB |
Output is correct |
| 8 |
Correct |
27 ms |
592 KB |
Output is correct |
| 9 |
Correct |
40 ms |
1488 KB |
Output is correct |
| 10 |
Correct |
94 ms |
1744 KB |
Output is correct |
| 11 |
Correct |
105 ms |
2504 KB |
Output is correct |
| 12 |
Correct |
130 ms |
3692 KB |
Output is correct |
| 13 |
Correct |
163 ms |
3744 KB |
Output is correct |
| 14 |
Correct |
182 ms |
4916 KB |
Output is correct |
| 15 |
Correct |
154 ms |
9940 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1356 ms |
11416 KB |
Output is correct |
| 2 |
Correct |
1506 ms |
10308 KB |
Output is correct |
| 3 |
Correct |
1947 ms |
15216 KB |
Output is correct |
| 4 |
Correct |
166 ms |
4996 KB |
Output is correct |
| 5 |
Correct |
358 ms |
8132 KB |
Output is correct |
| 6 |
Correct |
626 ms |
14584 KB |
Output is correct |
| 7 |
Correct |
607 ms |
18780 KB |
Output is correct |
| 8 |
Correct |
1105 ms |
36220 KB |
Output is correct |
| 9 |
Correct |
1743 ms |
24884 KB |
Output is correct |
| 10 |
Correct |
2354 ms |
72652 KB |
Output is correct |
| 11 |
Correct |
2324 ms |
28248 KB |
Output is correct |
| 12 |
Correct |
2043 ms |
27448 KB |
Output is correct |
| 13 |
Correct |
2198 ms |
28356 KB |
Output is correct |
| 14 |
Correct |
3011 ms |
35344 KB |
Output is correct |
| 15 |
Correct |
3883 ms |
36120 KB |
Output is correct |
| 16 |
Correct |
3429 ms |
46196 KB |
Output is correct |
| 17 |
Correct |
3558 ms |
51308 KB |
Output is correct |
