#include <bits/stdc++.h>
#include "floppy.h"
#ifdef BLAT
#include "debug/debug.hpp"
#else
#define debug(x...)
#endif
using namespace std;
void dfs(int node, string &bits, const vector <pair <int, int>> &sons) {
if (sons[node].first == -1) bits += '0';
else
bits += '1';
if (sons[node].second == -1) bits += '0';
else bits += '1';
if (sons[node].first != -1)
dfs(sons[node].first, bits, sons);
if (sons[node].second != -1)
dfs(sons[node].second, bits, sons);
}
void read_array(int subtask_id, const vector <int> &v) {
int n = v.size();
stack <int> st;
vector <pair <int, int>> sons(n, make_pair(-1, -1));
vector <bool> isroot(n, true);
for (int i = 0; i < n; i++) {
while (st.size() && v[i] > v[st.top()])
st.pop();
if (st.size()) {
isroot[i] = false;
sons[st.top()].second = i;
}
st.push(i);
}
while (st.size()) st.pop();
for (int i = n - 1; i >= 0; i--) {
while (st.size() && v[i] > v[st.top()])
st.pop();
if (st.size()) {
sons[st.top()].first = i;
isroot[i] = false;
}
st.push(i);
}
debug(sons);
string bits;
for (int i = 0; i < n; i++)
if (isroot[i])
dfs(i, bits, sons);
debug(bits);
save_to_floppy(bits);
}
void buildTree(int n, int node, int p, const string &bits, vector <pair <int, int>> &segments) {
if (bits[p] == '1') {
segments[node].first++;
buildTree(n, node + 1, p + 2, bits, segments);
segments[node].first += segments[node + 1].first + segments[node + 1].second;
}
if (bits[p + 1] == '1') {
int rnode = node + segments[node].first + 1;
int nextp = p + 2 * (segments[node].first + 1);
segments[node].second++;
buildTree(n, rnode, nextp, bits, segments);
segments[node].second += segments[rnode].first + segments[rnode].second;
}
}
void buildSegments(int node, int lnodes, const vector <pair <int, int>> &subtreesize,
vector <pair <int, int>> &segments, vector <int> &parent, int parentnode = -1) {
int realnode = subtreesize[node].first + lnodes;
segments[realnode] = subtreesize[node];
parent[realnode] = parentnode;
if (subtreesize[node].first != 0) {
buildSegments(node + 1, lnodes, subtreesize, segments, parent, realnode);
}
if (subtreesize[node].second != 0)
buildSegments(node + subtreesize[node].first + 1, lnodes + subtreesize[node].first + 1,
subtreesize, segments, parent, realnode);
}
void dfsDepth(int node, vector <int> &depth, vector <vector <int>> &g, int parent = -1) {
for (auto it : g[node])
if (it != parent) {
depth[it] = 1 + depth[node];
dfsDepth(it, depth, g, node);
}
}
int getLCA(int x, int y, vector <int> &depth, vector <vector <int>> &parent) {
if (depth[x] < depth[y])
swap(x, y);
for (int step = 16; step >= 0; step--)
if (depth[parent[step][x]] >= depth[y])
x = parent[step][x];
if (x == y)
return x;
for (int step = 16; step >= 0; step--)
if (parent[step][x] != parent[step][y]) {
x = parent[step][x];
y = parent[step][y];
}
assert(parent[0][x] == parent[0][y]);
return parent[0][x];
}
vector <int> solve_queries(int subtask_id, int N, const string &bits, const vector<int> &a, const vector<int> &b) {
vector <pair <int, int>> subtreesize(N), segments(N);
vector <vector <int>> parent(17, vector <int>(N));
int p = 0, root = 0;
buildTree(N, 0, p, bits, subtreesize);
buildSegments(0, 0, subtreesize, segments, parent[0]);
vector <vector <int>> g(N);
for (int i = 0; i < N; i++) {
if (parent[0][i] == -1) {
root = i;
parent[0][i] = i;
}
else {
g[i].push_back(parent[0][i]);
g[parent[0][i]].push_back(i);
}
}
for (int k = 1; k < 17; k++)
for (int i = 0; i < N; i++)
parent[k][i] = parent[k - 1][parent[k - 1][i]];
vector <int> depth(N);
dfsDepth(root, depth, g, -1);
debug(parent);
debug(depth);
vector <int> answers(a.size());
for (int i = 0; i < a.size(); i++) {
int x = a[i];
int y = b[i];
answers[i] = getLCA(x, y, depth, parent);
}
return answers;
}
/*
3
4 10
40 20 30 10
0 0 0
0 1 0
0 2 0
0 3 0
1 1 1
1 2 2
1 3 2
2 2 2
2 3 2
3 3 3
3
8 5
40 10 15 36 92 31 16 33
1 3 3
2 5 4
0 2 0
0 4 4
1 7 4
*/
Compilation message
floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:151:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
151 | for (int i = 0; i < a.size(); i++) {
| ~~^~~~~~~~~~
stub.cpp: In function 'void run2()':
stub.cpp:101:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
101 | if (query_answers.size() != M) {
| ~~~~~~~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
804 KB |
Output is correct |
| 2 |
Correct |
2 ms |
808 KB |
Output is correct |
| 3 |
Correct |
2 ms |
776 KB |
Output is correct |
| 4 |
Correct |
2 ms |
804 KB |
Output is correct |
| 5 |
Correct |
2 ms |
808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
4500 KB |
Output is correct |
| 2 |
Correct |
33 ms |
4628 KB |
Output is correct |
| 3 |
Correct |
28 ms |
5064 KB |
Output is correct |
| 4 |
Correct |
25 ms |
4880 KB |
Output is correct |
| 5 |
Correct |
25 ms |
4624 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
114 ms |
17176 KB |
Output is correct |
| 2 |
Correct |
134 ms |
17172 KB |
Output is correct |
| 3 |
Correct |
101 ms |
19496 KB |
Output is correct |
| 4 |
Correct |
126 ms |
18548 KB |
Output is correct |
| 5 |
Correct |
109 ms |
17196 KB |
Output is correct |
