| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 655601 |
2022-11-05T00:09:48 Z |
rafatoa |
Regions (IOI09_regions) |
C++17 |
|
85 ms |
121536 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]; R[h[1]].pb(1);
for(int i=2; i<=n; i++){
int p; cin >> p;
adj[p].pb(i);
cin >> h[i];
R[h[i]].pb(i);
}
vi in(n+1), sub(n+1);
int time = 0;
function<void(int)> dfs = [&](int s){
in[s] = time++;
sub[s] = 1;
for(auto u:adj[s]){
dfs(u);
sub[s] += sub[u];
}
};
dfs(1);
for(int i=1; i<=r; i++)
sort(all(R[i]), [&](int a, int b){
return in[a] < in[b];
});
int sq = sqrt(n);
map<int, int> mp;
map<pi, int> ans;
function<void(int)> dfs2 = [&](int s){
if(R[h[s]].size() > sq)
for(auto &[el, ti]:mp)
ans[{el, h[s]}] += ti;
mp[h[s]]++;
for(auto u:adj[s])
dfs2(u);
mp[h[s]]--;
if(mp[h[s]] == 0) mp.erase(h[s]);
};
dfs2(1);
for(int i=1; i<=r; i++){
if(R[i].size() <= sq) continue;
function<void(int, int)> dfs3 = [&](int s, int cnt){
if(h[s] != i && cnt > 0) ans[{i, h[s]}] += cnt;
if(h[s] == i) cnt++;
for(auto u:adj[s])
dfs3(u, cnt);
};
dfs3(1, 0);
}
while(q--){
int r1, r2; cin >> r1 >> r2;
if(r1 > sq || r2 > sq){
cout << ans[{r1, r2}] << endl;
} else {
int sum = 0;
for(int i=0; i<R[r1].size(); i++)
for(int j=0; j<R[r2].size(); j++)
if(in[R[r1][i]] <= in[R[r2][j]] && in[R[r2][j]] < in[R[r1][i]]+sub[R[r1][i]]) sum++;
cout << sum << "\n";
}
}
}
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 lambda function:
regions.cpp:67:21: 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[h[s]].size() > sq)
| ~~~~~~~~~~~~~~~^~~~
regions.cpp: In function 'void solve()':
regions.cpp:81:18: 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]
81 | if(R[i].size() <= sq) continue;
| ~~~~~~~~~~~~^~~~~
regions.cpp:98: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]
98 | for(int i=0; i<R[r1].size(); i++)
| ~^~~~~~~~~~~~~
regions.cpp:99: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]
99 | for(int j=0; j<R[r2].size(); j++)
| ~^~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:111:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
111 | freopen("in.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:112:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
112 | freopen("out.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
75 ms |
121428 KB |
Unexpected end of file - int32 expected |
| 2 |
Incorrect |
76 ms |
121388 KB |
Unexpected end of file - int32 expected |
| 3 |
Incorrect |
76 ms |
121388 KB |
Unexpected end of file - int32 expected |
| 4 |
Incorrect |
78 ms |
121384 KB |
Unexpected end of file - int32 expected |
| 5 |
Incorrect |
76 ms |
121480 KB |
Unexpected end of file - int32 expected |
| 6 |
Incorrect |
76 ms |
121476 KB |
Unexpected end of file - int32 expected |
| 7 |
Incorrect |
77 ms |
121476 KB |
Unexpected end of file - int32 expected |
| 8 |
Incorrect |
77 ms |
121536 KB |
Unexpected end of file - int32 expected |
| 9 |
Incorrect |
76 ms |
121392 KB |
Unexpected end of file - int32 expected |
| 10 |
Incorrect |
76 ms |
121412 KB |
Unexpected end of file - int32 expected |
| 11 |
Incorrect |
76 ms |
121464 KB |
Unexpected end of file - int32 expected |
| 12 |
Incorrect |
80 ms |
121476 KB |
Unexpected end of file - int32 expected |
| 13 |
Incorrect |
75 ms |
121480 KB |
Unexpected end of file - int32 expected |
| 14 |
Incorrect |
78 ms |
121360 KB |
Unexpected end of file - int32 expected |
| 15 |
Incorrect |
76 ms |
121416 KB |
Unexpected end of file - int32 expected |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
84 ms |
121440 KB |
Unexpected end of file - int32 expected |
| 2 |
Incorrect |
77 ms |
121388 KB |
Unexpected end of file - int32 expected |
| 3 |
Incorrect |
79 ms |
121416 KB |
Unexpected end of file - int32 expected |
| 4 |
Incorrect |
75 ms |
121472 KB |
Unexpected end of file - int32 expected |
| 5 |
Incorrect |
77 ms |
121484 KB |
Unexpected end of file - int32 expected |
| 6 |
Incorrect |
77 ms |
121480 KB |
Unexpected end of file - int32 expected |
| 7 |
Incorrect |
80 ms |
121484 KB |
Unexpected end of file - int32 expected |
| 8 |
Incorrect |
81 ms |
121460 KB |
Unexpected end of file - int32 expected |
| 9 |
Incorrect |
85 ms |
121436 KB |
Unexpected end of file - int32 expected |
| 10 |
Incorrect |
77 ms |
121488 KB |
Unexpected end of file - int32 expected |
| 11 |
Incorrect |
79 ms |
121476 KB |
Unexpected end of file - int32 expected |
| 12 |
Incorrect |
76 ms |
121400 KB |
Unexpected end of file - int32 expected |
| 13 |
Incorrect |
77 ms |
121416 KB |
Unexpected end of file - int32 expected |
| 14 |
Incorrect |
78 ms |
121460 KB |
Unexpected end of file - int32 expected |
| 15 |
Incorrect |
77 ms |
121416 KB |
Unexpected end of file - int32 expected |
| 16 |
Incorrect |
81 ms |
121484 KB |
Unexpected end of file - int32 expected |
| 17 |
Incorrect |
79 ms |
121488 KB |
Unexpected end of file - int32 expected |
