| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 427784 |
2021-06-14T22:35:14 Z |
Odavey |
Regions (IOI09_regions) |
C++17 |
|
2695 ms |
95324 KB |
//
// ~oisín~ C++ Template
//
#include <bits/stdc++.h>
#define MX_N 200005
#define mp make_pair
#define mod7 1000000007
#define modpi 314159
#define PI 3.141592653589793238
#define pb push_back
#define FastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define All(a) a.begin(),a.end()
#define fi first
#define se second
#define ll long long int
#define ull unsigned long long int
int kx[8] = {+2, +2, -2, -2, +1, +1, -1, -1};
int ky[8] = {+1, -1, +1, -1, +2, -2, +2, -2};
int d9x[9] = {+1, +1, +1, +0, +0, +0, -1, -1, -1};
int d9y[9] = {+1, +0, -1, +1, +0, -1, +1, +0, -1};
int dx4[4] = {+0, +0, +1, -1};
int dy4[4] = {+1, -1, +0, +0};
ll gcd(ull a, ull b){
return (a==0)?b:gcd(b%a,a);
}
ll lcm(ull a, ull b){
return a*(b/gcd(a,b));
}
const long long INF = 1e18;
using namespace std;
int N, R, Q;
int H[MX_N];
int p[MX_N];
vector<int> adj[MX_N];
vector<int> r[MX_N];
vector<pair<int, bool> > ord;
void dfs(int at){
ord.pb({at, 0});
r[H[at]].pb((int)ord.size()-1);
for(int to : adj[at]){
if(p[at] == to){
continue;
}
dfs(to);
}
ord.pb({at, 1});
r[H[at]].pb((int)ord.size()-1);
}
//map<pair<int, int>, int> cache;
//int cache[5000][5000];
map<int, int> cache[MX_N];
int main(){
cin >> N >> R >> Q;
int c = sqrt(N);
// int c = 1000000000;
cin >> H[0];
--H[0];
for(int i=1;i<N;++i){
cin >> p[i] >> H[i];
--p[i], --H[i];
adj[p[i]].pb(i);
}
dfs(0);
for(int j=0;j<R;++j){
if((int)r[j].size() >= c){
for(int i=0;i<R;++i){
if(i == j){
continue;
}
int x = 0, y = 0;
int cur;
if(r[i][0] < r[j][0]){
cur = r[i][0];
++x;
}else{
cur = r[j][0];
++y;
}
int cntA = 0, cntB = 0;
int ans = 0;
while(true){
auto P = ord[cur];
if(H[P.fi] == i){
if(P.se == 0){
++cntA;
}else{
--cntA;
}
}else{
if(P.se == 0){
++cntB;
ans += cntA;
}else{
--cntB;
}
}
if(x == r[i].size() && y == r[j].size()){
break;
}else if(x == r[i].size()){
cur = r[j][y];
++y;
}else if(y == r[j].size()){
cur = r[i][x];
++x;
}else{
if(r[i][x] < r[j][y]){
cur = r[i][x];
++x;
}else{
cur = r[j][y];
++y;
}
}
}
cache[i][j] = ans;
//cache[make_pair(i, j)] = ans;
//cache[i][j] = ans;
}
}
}
for(int i=0;i<R;++i){
if((int)r[i].size() >= c){
for(int j=0;j<R;++j){
if(i == j){
continue;
}
int x = 0, y = 0;
int cur;
if(r[i][0] < r[j][0]){
cur = r[i][0];
++x;
}else{
cur = r[j][0];
++y;
}
int cntA = 0, cntB = 0;
int ans = 0;
while(true){
auto P = ord[cur];
if(H[P.fi] == i){
if(P.se == 0){
++cntA;
}else{
--cntA;
}
}else{
if(P.se == 0){
++cntB;
ans += cntA;
}else{
--cntB;
}
}
if(x == r[i].size() && y == r[j].size()){
break;
}else if(x == r[i].size()){
cur = r[j][y];
++y;
}else if(y == r[j].size()){
cur = r[i][x];
++x;
}else{
if(r[i][x] < r[j][y]){
cur = r[i][x];
++x;
}else{
cur = r[j][y];
++y;
}
}
}
cache[i][j] = ans;
//cache[make_pair(i, j)] = ans;
// if(i == j){
// continue;
// }
// vector<int> tmp;
// for(auto P : r[i]){
// tmp.pb(P);
// }
// for(auto P : r[j]){
// tmp.pb(P);
// }
// sort(All(tmp));
// int cntA = 0, cntB = 0;
// int ans = 0;
// for(auto ii : tmp){
// auto P = ord[ii];
// if(H[P.fi] == i){
// if(P.se == 0){
// ++cntA;
// }else{
// --cntA;
// }
// }else{
// if(P.se == 0){
// ++cntB;
// ans += cntA;
// }else{
// --cntB;
// }
// }
// }
// //cache[i][j] = ans;
// cache[make_pair(i, j)] = ans;
}
}
}
while(Q--){
int r1, r2;
cin >> r1 >> r2;
--r1, --r2;
if((int)r[r1].size() >= c || (int)r[r2].size() >= c){
// cout << cache[make_pair(r1, r2)] << endl;
cout << cache[r1][r2] << endl;
cout.flush();
}else{
int x = 0, y = 0;
int cur;
if(r[r1][0] < r[r2][0]){
cur = r[r1][0];
++x;
}else{
cur = r[r2][0];
++y;
}
int cntA = 0, cntB = 0;
int ans = 0;
while(true){
auto P = ord[cur];
if(H[P.fi] == r1){
if(P.se == 0){
++cntA;
}else{
--cntA;
}
}else{
if(P.se == 0){
++cntB;
ans += cntA;
}else{
--cntB;
}
}
if(x == r[r1].size() && y == r[r2].size()){
break;
}else if(x == r[r1].size()){
cur = r[r2][y];
++y;
}else if(y == r[r2].size()){
cur = r[r1][x];
++x;
}else{
if(r[r1][x] < r[r2][y]){
cur = r[r1][x];
++x;
}else{
cur = r[r2][y];
++y;
}
}
}
cout << ans << endl;
cout.flush();
}
}
}
Compilation message
regions.cpp: In function 'int main()':
regions.cpp:108:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | if(x == r[i].size() && y == r[j].size()){
| ~~^~~~~~~~~~~~~~
regions.cpp:108:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | if(x == r[i].size() && y == r[j].size()){
| ~~^~~~~~~~~~~~~~
regions.cpp:110:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | }else if(x == r[i].size()){
| ~~^~~~~~~~~~~~~~
regions.cpp:113:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | }else if(y == r[j].size()){
| ~~^~~~~~~~~~~~~~
regions.cpp:166:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
166 | if(x == r[i].size() && y == r[j].size()){
| ~~^~~~~~~~~~~~~~
regions.cpp:166:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
166 | if(x == r[i].size() && y == r[j].size()){
| ~~^~~~~~~~~~~~~~
regions.cpp:168:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
168 | }else if(x == r[i].size()){
| ~~^~~~~~~~~~~~~~
regions.cpp:171:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
171 | }else if(y == r[j].size()){
| ~~^~~~~~~~~~~~~~
regions.cpp:258:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
258 | if(x == r[r1].size() && y == r[r2].size()){
| ~~^~~~~~~~~~~~~~~
regions.cpp:258:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
258 | if(x == r[r1].size() && y == r[r2].size()){
| ~~^~~~~~~~~~~~~~~
regions.cpp:260:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
260 | }else if(x == r[r1].size()){
| ~~^~~~~~~~~~~~~~~
regions.cpp:263:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
263 | }else if(y == r[r2].size()){
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
29 ms |
38488 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
31 ms |
38452 KB |
Execution killed with signal 11 |
| 3 |
Runtime error |
29 ms |
38500 KB |
Execution killed with signal 11 |
| 4 |
Correct |
16 ms |
19016 KB |
Output is correct |
| 5 |
Correct |
26 ms |
19144 KB |
Output is correct |
| 6 |
Runtime error |
31 ms |
38668 KB |
Execution killed with signal 11 |
| 7 |
Correct |
62 ms |
19096 KB |
Output is correct |
| 8 |
Correct |
35 ms |
19220 KB |
Output is correct |
| 9 |
Correct |
101 ms |
19868 KB |
Output is correct |
| 10 |
Correct |
160 ms |
19736 KB |
Output is correct |
| 11 |
Correct |
182 ms |
21436 KB |
Output is correct |
| 12 |
Correct |
101 ms |
20864 KB |
Output is correct |
| 13 |
Correct |
359 ms |
22580 KB |
Output is correct |
| 14 |
Correct |
515 ms |
22980 KB |
Output is correct |
| 15 |
Correct |
884 ms |
27600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1567 ms |
26900 KB |
Output is correct |
| 2 |
Correct |
1773 ms |
25560 KB |
Output is correct |
| 3 |
Correct |
2695 ms |
30756 KB |
Output is correct |
| 4 |
Runtime error |
68 ms |
42536 KB |
Execution killed with signal 11 |
| 5 |
Runtime error |
61 ms |
47540 KB |
Execution killed with signal 11 |
| 6 |
Runtime error |
75 ms |
45708 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
96 ms |
48148 KB |
Execution killed with signal 11 |
| 8 |
Runtime error |
155 ms |
63524 KB |
Execution killed with signal 11 |
| 9 |
Runtime error |
168 ms |
61860 KB |
Execution killed with signal 11 |
| 10 |
Runtime error |
197 ms |
75920 KB |
Execution killed with signal 11 |
| 11 |
Runtime error |
273 ms |
61044 KB |
Execution killed with signal 11 |
| 12 |
Runtime error |
216 ms |
64256 KB |
Execution killed with signal 11 |
| 13 |
Runtime error |
218 ms |
65700 KB |
Execution killed with signal 11 |
| 14 |
Runtime error |
254 ms |
64856 KB |
Execution killed with signal 11 |
| 15 |
Runtime error |
1911 ms |
77548 KB |
Execution killed with signal 11 |
| 16 |
Runtime error |
248 ms |
95324 KB |
Execution killed with signal 11 |
| 17 |
Runtime error |
229 ms |
91932 KB |
Execution killed with signal 11 |
