QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#415072 | #33. Cat in a tree | x-camp | 51 | 531ms | 62056kb | C++17 | 3.6kb | 2024-05-20 09:08:46 | 2024-05-20 09:08:48 |
Judging History
answer
#include <iostream>
#include <vector>
#include <cstring>
#include <set>
/*
centroid decomposition to solve Cat in Tree problem
*/
using namespace std;
#define INF (1e9)
const int MX = 200001; // Adjust the maximum number of nodes as needed
vector<int> adj[MX];
bool visited[MX];
int subtreeSize[MX];
int min_dist[MX];
vector<vector<pair<int, int>>> ancestors;
int N, D;
int dfs_depth;
set<pair<int,int>> nodes;
int ans;
int dfs(int node, int parent, int depth = 1) {
subtreeSize[node] = 1;
nodes.insert({-depth,node});
for (int child : adj[node]) {
if (child != parent && !visited[child]) {
subtreeSize[node] += dfs(child, node, depth+1);
}
}
return subtreeSize[node];
}
int findCentroid(int node, int parent, int treeSize) {
for (int child : adj[node]) {
if (child != parent && !visited[child]) {
if (subtreeSize[child] *2 >= treeSize)
return findCentroid(child, node, treeSize);
}
}
return node;
}
void get_dists(int node, int centroid, int parent = -1, int cur_dist = 1) {
for (int child : adj[node]) {
if (child == parent || visited[child]) { continue; }
// cur_dist++;
get_dists(child, centroid, node, cur_dist+1);
// cur_dist--;
}
ancestors[node].push_back({centroid, cur_dist});
}
int cnt = 0;
void decompose(int centroid) {
cnt ++;
for (int child : adj[centroid]) {
if (visited[child]) { continue; }
get_dists(child, centroid, centroid);
}
// Mark the centroid and its subtree as visited
visited[centroid] = true;
for (int child : adj[centroid]) {
if (!visited[child]) {
// Recursively decompose the subtrees
int subtreeSize = dfs(child, centroid,1);
int childCentroid = findCentroid(child, centroid, subtreeSize);
if (subtreeSize > 1)
decompose(childCentroid);
}
}
}
int centroidDecomposition(int root) {
int treeSize = dfs(root, -1);
int centroid = findCentroid(root, -1, treeSize);
// Process the centroid and its subtree
decompose(centroid);
return centroid;
}
void paintRed (int node) {
for (auto &[ancestor, dist] : ancestors[node]) {
if (dist < min_dist[ancestor])
min_dist[ancestor] = dist;
}
min_dist[node] = 0;
}
/* min distance from a node to any red note*/
int query(int node) {
int ans = min_dist[node];
for (auto &[ancestor, dist] : ancestors[node]) {
if (!dist) { continue; }
/*
* The distance between `node` and a red painted node is the sum of
* the distance from `node` to one of its ancestors (`dist`) and the
* distance from this ancestor to the nearest red node
* (`min_dist[ancestor]`).
*/
ans = min(ans, dist + min_dist[ancestor]);
}
return ans;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> D;
for (int i = 1; i <= N - 1; ++i) {
int u;
cin >> u;
adj[i].push_back(u);
adj[u].push_back(i);
}
memset(min_dist, 0x3f, sizeof min_dist);
ancestors.assign(N+1, vector<pair<int, int>>());
centroidDecomposition(1);
auto cur = (*nodes.begin()).second;
ans ++ ;
paintRed(cur);
nodes.erase(nodes.begin());
for (auto it = nodes.begin(); it != nodes.end(); it++) {
auto next = *it;
if (query(next.second) >= D) {
paintRed(next.second);
ans++;
}
}
cout << ans ;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 11
Accepted
Test #1:
score: 11
Accepted
time: 0ms
memory: 9972kb
input:
10 2 0 0 2 2 0 3 4 7 2
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 2ms
memory: 9008kb
input:
10 3 0 0 2 1 4 4 3 1 7
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Accepted
time: 0ms
memory: 9784kb
input:
12 1 0 0 1 3 1 0 2 1 3 2 2
output:
12
result:
ok single line: '12'
Test #4:
score: 0
Accepted
time: 2ms
memory: 9636kb
input:
12 4 0 0 1 2 0 0 4 7 7 9 10
output:
3
result:
ok single line: '3'
Test #5:
score: 0
Accepted
time: 0ms
memory: 10044kb
input:
14 2 0 1 2 3 0 1 5 1 4 0 3 11 9
output:
8
result:
ok single line: '8'
Test #6:
score: 0
Accepted
time: 2ms
memory: 9384kb
input:
14 4 0 0 2 3 4 2 6 3 6 9 3 3 2
output:
3
result:
ok single line: '3'
Test #7:
score: 0
Accepted
time: 2ms
memory: 9924kb
input:
16 2 0 0 0 1 2 3 2 6 6 0 4 11 0 12 2
output:
11
result:
ok single line: '11'
Test #8:
score: 0
Accepted
time: 2ms
memory: 9012kb
input:
16 3 0 0 0 3 2 2 0 2 8 4 6 11 8 3 5
output:
6
result:
ok single line: '6'
Test #9:
score: 0
Accepted
time: 0ms
memory: 9008kb
input:
18 1 0 0 2 2 2 1 0 3 1 4 2 2 12 0 6 10 13
output:
18
result:
ok single line: '18'
Test #10:
score: 0
Accepted
time: 1ms
memory: 9088kb
input:
18 5 0 0 2 1 0 2 6 5 8 5 0 8 5 4 12 7 10
output:
4
result:
ok single line: '4'
Test #11:
score: 0
Accepted
time: 1ms
memory: 9296kb
input:
18 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output:
18
result:
ok single line: '18'
Test #12:
score: 0
Accepted
time: 2ms
memory: 10000kb
input:
18 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output:
17
result:
ok single line: '17'
Test #13:
score: 0
Accepted
time: 0ms
memory: 9436kb
input:
17 1 0 1 1 0 0 1 2 0 1 0 2 1 2 2 2 2
output:
17
result:
ok single line: '17'
Test #14:
score: 0
Accepted
time: 1ms
memory: 9260kb
input:
17 2 0 1 0 1 1 0 2 1 2 1 1 0 1 2 0 0
output:
14
result:
ok single line: '14'
Test #15:
score: 0
Accepted
time: 2ms
memory: 10040kb
input:
18 5 0 0 1 1 0 1 2 2 2 1 0 0 1 0 1 1 0
output:
1
result:
ok single line: '1'
Test #16:
score: 0
Accepted
time: 2ms
memory: 9988kb
input:
18 1 0 1 2 0 1 0 4 0 2 3 0 3 2 1 3 4 2
output:
18
result:
ok single line: '18'
Test #17:
score: 0
Accepted
time: 0ms
memory: 9972kb
input:
18 2 0 0 0 1 2 2 3 3 1 3 4 1 1 4 2 4 0
output:
13
result:
ok single line: '13'
Test #18:
score: 0
Accepted
time: 2ms
memory: 10036kb
input:
18 3 0 1 1 3 1 4 2 1 0 2 0 0 1 1 3 0 3
output:
5
result:
ok single line: '5'
Test #19:
score: 0
Accepted
time: 0ms
memory: 9072kb
input:
18 6 0 0 2 3 4 3 3 1 6 1 2 0 2 0 5 2 4
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 2ms
memory: 9980kb
input:
18 7 0 1 0 3 2 0 6 3 4 4 3 2 6 3 6 0 0
output:
1
result:
ok single line: '1'
Subtask #2:
score: 40
Accepted
Dependency #1:
100%
Accepted
Test #21:
score: 40
Accepted
time: 4ms
memory: 10624kb
input:
1500 1000 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ...
output:
2
result:
ok single line: '2'
Test #22:
score: 0
Accepted
time: 0ms
memory: 10236kb
input:
500 1 0 1 1 1 1 5 5 2 4 4 10 0 0 11 12 6 13 5 17 2 13 12 19 12 8 7 18 5 9 10 15 1 25 21 7 32 29 14 22 12 34 13 1 10 0 20 4 6 44 38 19 12 9 17 20 51 5 3 23 46 39 25 7 42 37 55 13 14 30 46 9 71 47 55 61 43 39 1 76 0 49 8 80 51 51 71 55 44 79 25 80 24 68 15 41 88 72 76 72 38 83 94 88 69 17 9 49 75 64 3...
output:
500
result:
ok single line: '500'
Test #23:
score: 0
Accepted
time: 2ms
memory: 9868kb
input:
500 5 0 1 2 0 3 5 0 2 0 3 10 1 3 5 13 8 8 16 16 4 17 5 1 17 6 1 17 9 20 0 27 27 1 14 24 30 17 5 37 37 9 33 7 20 39 24 29 20 33 19 32 26 13 33 31 21 31 11 20 50 35 34 16 47 17 5 48 55 60 66 57 43 10 68 69 69 34 75 27 41 3 56 8 32 41 85 55 70 5 57 48 61 41 78 19 12 85 73 62 18 79 95 47 39 61 67 88 18 ...
output:
89
result:
ok single line: '89'
Test #24:
score: 0
Accepted
time: 2ms
memory: 10388kb
input:
500 10 0 1 1 0 1 0 6 6 8 1 4 0 10 0 13 8 11 16 18 1 17 7 21 22 1 22 9 26 1 4 1 21 5 18 6 7 35 4 31 5 38 36 31 37 25 17 8 28 36 12 26 20 9 11 20 42 38 17 29 42 29 38 28 39 46 39 3 46 22 16 34 25 14 3 21 73 62 77 78 29 43 3 25 48 3 47 17 54 3 43 47 43 42 62 12 44 38 29 75 62 37 96 91 47 97 104 15 84 4...
output:
23
result:
ok single line: '23'
Test #25:
score: 0
Accepted
time: 3ms
memory: 9988kb
input:
1000 1 0 0 0 2 0 4 3 4 4 2 9 4 1 12 2 12 7 12 13 1 12 20 17 5 8 3 7 0 11 18 28 2 29 26 34 24 5 24 22 38 30 0 30 19 17 9 45 32 14 47 42 29 47 5 2 1 44 23 16 48 3 51 28 44 16 24 31 8 49 0 6 12 39 6 13 2 74 77 0 25 78 67 43 83 32 22 69 38 57 32 62 23 12 22 53 85 88 91 3 4 42 96 93 20 59 44 59 102 95 86...
output:
1000
result:
ok single line: '1000'
Test #26:
score: 0
Accepted
time: 3ms
memory: 9724kb
input:
1000 5 0 0 1 1 2 3 0 2 0 1 6 3 10 13 14 1 12 0 2 0 0 16 0 14 13 11 1 4 2 15 21 10 24 4 0 18 16 29 24 2 38 40 17 31 17 30 8 18 12 49 16 47 31 52 53 10 41 28 39 57 20 49 43 1 46 27 59 38 7 37 24 38 36 13 59 34 25 31 63 36 4 32 72 9 17 4 80 87 63 20 68 43 42 64 80 8 88 2 24 68 6 41 34 68 63 66 92 32 93...
output:
191
result:
ok single line: '191'
Test #27:
score: 0
Accepted
time: 0ms
memory: 9456kb
input:
1000 10 0 0 1 2 2 2 4 2 3 9 10 5 7 3 4 6 7 2 8 16 9 5 4 3 17 17 23 10 11 26 15 30 20 32 27 12 5 29 10 15 22 9 40 19 30 1 23 33 16 5 0 5 18 18 5 48 5 50 27 39 35 60 54 11 29 25 43 13 62 29 48 39 13 49 44 66 52 65 54 29 66 15 32 35 76 7 53 40 57 7 7 77 82 83 43 31 28 85 69 1 9 72 32 29 53 57 5 94 57 6...
output:
44
result:
ok single line: '44'
Test #28:
score: 0
Accepted
time: 0ms
memory: 10252kb
input:
1500 12 0 1 2 0 4 2 0 4 6 2 3 10 4 2 12 2 10 1 5 7 7 10 3 10 0 20 1 15 24 25 0 10 30 13 0 14 24 20 7 37 25 6 20 34 37 0 27 28 25 26 28 8 2 25 50 19 19 55 33 26 53 1 53 23 20 23 27 36 17 63 22 39 10 22 26 68 62 26 1 56 11 1 51 12 19 84 42 59 65 73 9 61 63 65 27 44 34 85 31 79 98 72 60 57 92 10 53 45 ...
output:
41
result:
ok single line: '41'
Test #29:
score: 0
Accepted
time: 0ms
memory: 10592kb
input:
1500 5 0 0 2 2 3 0 5 0 0 6 2 8 0 12 8 0 2 5 4 4 4 0 0 10 16 4 26 27 10 17 23 21 5 24 27 6 22 28 2 38 24 11 38 25 19 20 22 35 21 7 6 42 21 19 30 30 56 10 23 31 5 35 49 25 2 28 31 56 43 65 55 62 15 45 10 70 30 56 67 28 35 56 4 25 42 34 41 76 12 81 66 66 8 57 47 80 75 14 68 97 12 58 10 75 86 64 101 104...
output:
293
result:
ok single line: '293'
Test #30:
score: 0
Accepted
time: 3ms
memory: 10512kb
input:
1500 15 0 1 2 3 0 0 5 1 8 0 10 1 1 0 4 6 4 2 5 18 1 8 3 8 3 1 20 22 23 28 25 31 3 28 27 8 36 25 3 30 8 29 41 21 41 34 46 37 24 6 33 15 44 44 18 14 37 55 43 59 10 3 40 27 55 44 40 3 22 53 18 11 17 35 1 41 53 41 22 40 29 35 21 26 37 23 38 74 33 84 2 63 82 53 45 24 43 75 1 66 80 52 63 31 63 46 71 65 48...
output:
19
result:
ok single line: '19'
Test #31:
score: 0
Accepted
time: 4ms
memory: 10508kb
input:
1500 40 0 1 0 0 1 1 0 7 2 5 1 9 11 9 12 3 14 8 10 11 3 5 16 5 9 20 18 21 17 8 30 13 28 9 9 30 9 2 9 6 25 28 8 33 43 19 37 41 14 10 44 38 8 53 47 1 46 32 14 24 23 51 14 46 32 32 66 60 49 53 45 35 47 24 72 52 56 22 77 65 23 3 61 33 36 48 12 79 21 46 74 9 24 23 25 36 2 63 95 49 45 68 18 51 16 1 29 48 1...
output:
1
result:
ok single line: '1'
Test #32:
score: 0
Accepted
time: 3ms
memory: 10148kb
input:
1470 4 0 0 1 1 3 4 1 2 5 8 2 8 11 11 9 5 1 0 11 19 8 7 6 1 9 3 13 0 0 16 14 11 12 11 19 14 13 1 12 5 2 6 18 17 12 18 3 7 11 3 15 7 4 19 17 14 17 6 3 11 16 8 3 4 3 7 3 4 17 7 9 7 8 15 6 10 19 12 17 10 10 2 3 4 8 7 4 5 9 1 17 12 10 0 2 13 3 5 4 19 15 10 9 6 7 13 7 5 1 17 18 6 11 12 5 4 17 15 5 0 16 4 ...
output:
13
result:
ok single line: '13'
Test #33:
score: 0
Accepted
time: 3ms
memory: 10120kb
input:
1470 10 0 1 2 1 0 3 2 6 5 6 0 0 7 7 3 2 13 5 12 1 5 18 9 5 18 0 18 9 10 19 1 14 15 12 7 7 6 3 8 5 2 17 3 10 6 2 2 12 1 17 19 9 6 7 3 10 18 5 12 5 10 11 2 8 3 19 6 15 19 13 17 6 9 5 1 1 2 10 7 17 4 18 14 7 18 12 0 12 13 17 14 12 12 13 11 0 2 18 9 8 6 3 16 5 9 10 0 13 0 10 6 5 17 0 4 8 3 6 18 14 15 5 ...
output:
1
result:
ok single line: '1'
Test #34:
score: 0
Accepted
time: 3ms
memory: 9784kb
input:
1400 10 0 1 1 1 3 3 1 0 7 1 5 3 8 0 6 11 6 13 4 5 5 17 4 6 13 21 3 24 19 21 21 13 0 29 5 2 29 23 15 4 14 24 33 15 44 4 5 13 7 10 46 24 25 15 48 43 16 0 57 35 43 35 33 50 20 46 21 4 6 1 1 42 8 44 8 17 30 70 40 0 8 3 80 10 14 26 66 2 45 1 46 73 0 8 89 25 4 60 51 26 61 50 85 29 38 17 84 88 30 44 1 64 1...
output:
5
result:
ok single line: '5'
Test #35:
score: 0
Accepted
time: 3ms
memory: 10716kb
input:
1400 12 0 0 0 1 0 1 3 2 1 1 4 7 5 0 7 9 13 8 2 18 5 2 14 18 11 12 5 0 9 27 5 1 9 21 4 10 21 25 15 26 23 8 36 15 37 0 1 38 27 49 26 9 20 45 6 48 36 24 34 16 34 11 36 57 28 21 11 53 32 53 44 22 17 24 52 28 9 36 64 71 20 74 23 15 45 0 31 87 43 22 88 21 67 31 12 18 73 67 30 8 7 74 60 85 18 94 16 20 15 6...
output:
5
result:
ok single line: '5'
Test #36:
score: 0
Accepted
time: 3ms
memory: 10212kb
input:
1500 10 0 1 0 2 3 4 5 5 6 1 10 4 6 11 12 7 11 6 7 1 19 14 20 12 21 12 6 1 18 9 16 16 25 19 18 21 22 4 18 24 25 7 14 8 31 12 29 46 40 5 43 4 7 52 12 17 11 42 43 32 9 48 24 17 24 63 8 10 48 1 9 33 28 25 64 20 71 49 69 5 26 1 73 19 42 78 24 84 9 21 39 65 80 12 80 57 50 36 68 92 97 57 46 7 88 72 21 50 5...
output:
7
result:
ok single line: '7'
Test #37:
score: 0
Accepted
time: 3ms
memory: 9936kb
input:
1500 4 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 79 93 ...
output:
50
result:
ok single line: '50'
Test #38:
score: 0
Accepted
time: 4ms
memory: 10012kb
input:
1500 50 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...
output:
7
result:
ok single line: '7'
Test #39:
score: 0
Accepted
time: 0ms
memory: 10796kb
input:
1500 70 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...
output:
8
result:
ok single line: '8'
Test #40:
score: 0
Accepted
time: 0ms
memory: 10112kb
input:
1500 5 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100...
output:
301
result:
ok single line: '301'
Subtask #3:
score: 0
Time Limit Exceeded
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #41:
score: 49
Accepted
time: 159ms
memory: 49480kb
input:
190001 5 0 1 2 0 4 5 0 7 8 0 10 11 0 13 14 0 16 17 0 19 20 0 22 23 0 25 26 0 28 29 0 31 32 0 34 35 0 37 38 0 40 41 0 43 44 0 46 47 0 49 50 0 52 53 0 55 56 0 58 59 0 61 62 0 64 65 0 67 68 0 70 71 0 73 74 0 76 77 0 79 80 0 82 83 0 85 86 0 88 89 0 91 92 0 94 95 0 97 98 0 100 101 0 103 104 0 106 107 0 1...
output:
50462
result:
ok single line: '50462'
Test #42:
score: 0
Accepted
time: 493ms
memory: 59664kb
input:
100000 1 0 1 0 2 2 5 6 5 5 2 8 4 7 3 2 4 3 1 13 17 3 18 11 23 20 9 3 18 26 15 2 11 19 27 5 0 19 9 31 17 2 7 12 2 1 5 40 6 4 33 16 30 8 40 2 26 4 23 0 32 39 32 43 11 52 8 61 15 0 62 16 56 11 34 21 14 64 23 11 71 33 78 60 76 65 19 45 9 38 79 74 45 39 49 55 17 64 53 90 78 70 4 8 13 73 26 4 98 63 70 105...
output:
100000
result:
ok single line: '100000'
Test #43:
score: 0
Accepted
time: 519ms
memory: 62056kb
input:
100000 20 0 1 1 0 2 5 6 3 5 5 2 3 5 13 0 2 8 16 8 5 16 12 4 22 2 7 26 23 26 28 12 17 23 21 4 17 1 31 14 4 24 21 28 33 33 24 35 27 15 33 42 32 32 7 46 39 20 44 52 0 13 5 54 11 43 0 45 43 25 2 44 66 50 20 18 34 28 75 28 21 24 23 10 62 23 79 53 81 71 77 29 43 42 83 86 13 24 87 10 67 60 77 54 74 74 52 8...
output:
454
result:
ok single line: '454'
Test #44:
score: 0
Accepted
time: 531ms
memory: 61416kb
input:
100000 50 0 1 1 2 0 3 5 3 7 9 5 6 4 6 8 7 15 3 10 1 17 15 14 22 2 4 19 9 5 12 2 4 20 18 8 8 35 15 26 13 19 35 30 34 20 42 27 0 26 39 41 43 51 3 39 24 38 56 48 32 59 50 56 33 1 65 61 14 19 61 40 6 50 47 59 54 48 69 29 40 61 76 11 37 16 46 53 23 53 40 63 4 12 50 44 55 89 10 85 9 72 95 81 85 18 85 36 6...
output:
1
result:
ok single line: '1'
Test #45:
score: 0
Accepted
time: 490ms
memory: 59064kb
input:
100000 100 0 1 0 3 1 2 2 7 6 9 7 11 3 12 14 1 2 2 2 14 5 7 15 21 18 0 18 6 18 16 1 7 4 26 34 29 31 37 36 11 38 18 7 29 37 45 4 40 37 4 0 14 9 2 25 36 36 45 40 56 34 41 61 37 32 52 59 65 40 19 67 41 41 43 14 72 49 73 69 67 59 32 50 16 35 44 4 2 25 0 49 4 85 68 57 43 78 96 36 93 23 9 24 47 92 55 54 56...
output:
1
result:
ok single line: '1'
Test #46:
score: -49
Time Limit Exceeded
input:
200000 2 0 0 0 0 3 4 1 0 0 9 7 7 1 11 3 9 4 12 18 7 14 13 22 9 18 0 6 15 17 19 8 31 5 30 1 23 1 10 38 33 32 2 27 38 8 21 29 33 8 27 28 15 9 1 29 25 32 45 55 26 15 50 17 38 3 22 38 7 64 39 10 67 37 8 44 15 45 40 53 11 16 44 9 51 30 44 8 35 85 42 53 58 36 67 25 78 75 9 42 52 54 50 101 97 10 25 26 62 7...