| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 521842 |
2022-02-03T09:47:31 Z |
Vladth11 |
Regions (IOI09_regions) |
C++14 |
|
1682 ms |
131076 KB |
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
const int NMAX = 200001;
const int VMAX = 21;
const int INF = (1LL << 60);
const int MOD = 1000000007;
const int BLOCK = 318;
const int base = 31;
const int nr_of_bits = 21;
const int MMAX = NMAX / BLOCK + 5;
vector <int> v[NMAX], vertices[NMAX];
vector <pii> lista[NMAX];
int stamp;
int n, R, Q;
int sol[MMAX][25001];
int precalc[25001][MMAX];
int region[NMAX];
int bigR[NMAX];
int smallR[NMAX];
int bigIdx[NMAX];
int smallIdx[NMAX];
int cati[NMAX];
int stiva[NMAX];
int vf;
int countAbove[MMAX];
int timestamp;
pii timp[NMAX];
int preorder[NMAX + 1];
void DFS(int node, int p) {
stamp++;
timp[node].first = ++timestamp;
lista[region[node]].push_back({node, stamp});
if(bigIdx[region[node]] != 0) {
countAbove[bigIdx[region[node]]]++;
}
for(int i = 1; i <= MMAX; i++) {
sol[i][region[node]] += countAbove[i];
}
for(auto x : v[node]) {
if(x == p)
continue;
DFS(x, node);
}
stamp++;
timp[node].second = timestamp;
lista[region[node]].push_back({node, stamp});
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int i;
cin >> n >> R >> Q;
cin >> region[1];
vertices[region[1]].push_back(i);
cati[region[1]]++;
for(i = 2; i <= n; i++) {
int p;
cin >> p >> region[i];
v[p].push_back(i);
v[i].push_back(p);
vertices[region[i]].push_back(i);
cati[region[i]]++;
}
int cc = 0, sc = 0;
for(i = 1; i <= R; i++) {
if(cati[i] >= BLOCK) {
bigR[++cc] = i;
bigIdx[i] = cc;
} else {
smallR[++sc] = i;
smallIdx[i] = sc;
}
}
DFS(1, 0);
for(int i = 1; i <= R; i++) {
if(bigIdx[i] == 0) continue;
for(auto x : vertices[i]) {
preorder[timp[x].first] = 1;
preorder[timp[x].second + 1] = -1;
}
for(int j = 1; j <= n; j++) {
preorder[j] += preorder[j - 1];
}
for(int j = 1; j <= sc; j++) {
for(auto x : vertices[j])
precalc[j][bigIdx[i]] += (preorder[timp[x].second] - preorder[timp[x].first - 1]);
}
for(int j = 1; j <= n; j++)
preorder[j] = 0;
}
while(Q--) {
int a, b;
cin >> a >> b;
if(bigIdx[a] != 0) { /// Aia de sus mare
cout << sol[bigIdx[a]][b] << "\n";
} else if(bigIdx[b] != 0) { /// Aia de jos mare si aia de sus mica
cout << precalc[smallIdx[a]][bigIdx[b]] << "\n";
} else { /// Ambele mici
int i = 0;
int j = 0;
int deschise = 0;
vf = 0;
int rez = 0;
while(i < lista[a].size() && j < lista[b].size()) {
pii x = lista[a][i];
pii y = lista[b][j];
if(x.second < y.second) {
if(stiva[vf] == x.first) {
vf--;
deschise--;
} else {
stiva[++vf] = x.first;
deschise++;
}
i++;
} else {
if(stiva[vf] == y.first) {
vf--;
} else {
rez += deschise;
stiva[++vf] = y.first;
}
j++;
}
}
cout << rez;
}
cout.flush();
}
return 0;
}
Compilation message
regions.cpp:12:22: warning: overflow in conversion from 'long long int' to 'int' changes value from '1152921504606846976' to '0' [-Woverflow]
12 | const int INF = (1LL << 60);
| ~~~~~^~~~~~
regions.cpp: In function 'int main()':
regions.cpp:115:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | while(i < lista[a].size() && j < lista[b].size()) {
| ~~^~~~~~~~~~~~~~~~~
regions.cpp:115:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | while(i < lista[a].size() && j < lista[b].size()) {
| ~~^~~~~~~~~~~~~~~~~
regions.cpp: In function 'void DFS(int, int)':
regions.cpp:46:30: warning: iteration 632 invokes undefined behavior [-Waggressive-loop-optimizations]
46 | sol[i][region[node]] += countAbove[i];
| ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
regions.cpp:45:22: note: within this loop
45 | for(int i = 1; i <= MMAX; i++) {
| ~~^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8 ms |
17096 KB |
Time limit exceeded (wall clock) |
| 2 |
Execution timed out |
8 ms |
17096 KB |
Time limit exceeded (wall clock) |
| 3 |
Execution timed out |
8 ms |
17096 KB |
Time limit exceeded (wall clock) |
| 4 |
Execution timed out |
8 ms |
17096 KB |
Time limit exceeded (wall clock) |
| 5 |
Execution timed out |
8 ms |
17224 KB |
Time limit exceeded (wall clock) |
| 6 |
Execution timed out |
10 ms |
17920 KB |
Time limit exceeded (wall clock) |
| 7 |
Execution timed out |
10 ms |
17608 KB |
Time limit exceeded (wall clock) |
| 8 |
Execution timed out |
10 ms |
17736 KB |
Time limit exceeded (wall clock) |
| 9 |
Execution timed out |
13 ms |
18888 KB |
Time limit exceeded (wall clock) |
| 10 |
Execution timed out |
19 ms |
19144 KB |
Time limit exceeded (wall clock) |
| 11 |
Execution timed out |
26 ms |
19396 KB |
Time limit exceeded (wall clock) |
| 12 |
Execution timed out |
31 ms |
20800 KB |
Time limit exceeded (wall clock) |
| 13 |
Execution timed out |
41 ms |
20724 KB |
Time limit exceeded (wall clock) |
| 14 |
Execution timed out |
40 ms |
21056 KB |
Time limit exceeded (wall clock) |
| 15 |
Execution timed out |
54 ms |
25880 KB |
Time limit exceeded (wall clock) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
97 ms |
26928 KB |
Time limit exceeded (wall clock) |
| 2 |
Execution timed out |
103 ms |
26540 KB |
Time limit exceeded (wall clock) |
| 3 |
Execution timed out |
121 ms |
30512 KB |
Time limit exceeded (wall clock) |
| 4 |
Execution timed out |
172 ms |
30476 KB |
Time limit exceeded (wall clock) |
| 5 |
Execution timed out |
222 ms |
35768 KB |
Time limit exceeded (wall clock) |
| 6 |
Execution timed out |
330 ms |
56532 KB |
Time limit exceeded (wall clock) |
| 7 |
Execution timed out |
476 ms |
74644 KB |
Time limit exceeded (wall clock) |
| 8 |
Execution timed out |
638 ms |
82940 KB |
Time limit exceeded (wall clock) |
| 9 |
Execution timed out |
972 ms |
108704 KB |
Time limit exceeded (wall clock) |
| 10 |
Runtime error |
1146 ms |
131076 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
1328 ms |
131076 KB |
Execution killed with signal 9 |
| 12 |
Execution timed out |
1223 ms |
113760 KB |
Time limit exceeded (wall clock) |
| 13 |
Execution timed out |
1213 ms |
115564 KB |
Time limit exceeded (wall clock) |
| 14 |
Runtime error |
1436 ms |
131076 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
1443 ms |
131076 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
1432 ms |
131076 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
1682 ms |
131076 KB |
Execution killed with signal 9 |
