| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 954258 |
2024-03-27T14:30:17 Z |
TAhmed33 |
Floppy (RMI20_floppy) |
C++17 |
|
57 ms |
16544 KB |
#include <bits/stdc++.h>
using namespace std;
#include "floppy.h"
const int MAXN = 4e4 + 25;
int a[MAXN], n;
int nxt[MAXN], prv[MAXN];
vector <int> adj[MAXN];
string ret;
void dfs (int pos) {
sort(adj[pos].begin(), adj[pos].end());
if (adj[pos].empty()) {
ret += "00";
return;
}
if (adj[pos].size() == 1) {
if (adj[pos][0] > pos) {
ret += "01";
} else {
ret += "10";
}
dfs(adj[pos][0]);
} else {
ret += "11";
dfs(adj[pos][0]);
dfs(adj[pos][1]);
}
}
void read_array(int subtask_id, const std::vector<int> &v) {
n = v.size();
for (int i = 1; i <= n; i++) a[i] = v[i - 1];
stack <int> cur; cur.push(1);
for (int i = 2; i <= n; i++) {
while (!cur.empty() && a[cur.top()] < a[i]) {
nxt[cur.top()] = i;
cur.pop();
}
}
while (!cur.empty()) {
nxt[cur.top()] = -1;
cur.pop();
}
cur.push(n);
for (int i = n - 1; i >= 1; i--) {
while (!cur.empty() && a[cur.top()] < a[i]) {
prv[cur.top()] = i;
cur.pop();
}
}
while (!cur.empty()) {
prv[cur.top()] = -1;
cur.pop();
}
int root = -1;
for (int i = 1; i <= n; i++) {
if (nxt[i] == -1 && prv[i] == -1) {
root = i;
continue;
}
if (nxt[i] == -1) {
adj[prv[i]].push_back(i);
}
if (prv[i] == -1) {
adj[nxt[i]].push_back(i);
}
if (a[nxt[i]] < a[prv[i]]) {
adj[nxt[i]].push_back(i);
} else {
adj[prv[i]].push_back(i);
}
}
dfs(root);
save_to_floppy(ret);
}
int deg[MAXN];
vector <int> inorder;
int L[MAXN], R[MAXN];
int idx[MAXN];
int dp[20][MAXN], dep[MAXN];
void dfs2 (int pos) {
if (L[pos] != -1) {
dp[0][L[pos]] = pos;
dep[L[pos]] = 1 + dep[pos];
dfs(L[pos]);
}
inorder.push_back(pos);
if (R[pos] != -1) {
dp[0][R[pos]] = pos;
dep[R[pos]] = 1 + dep[pos];
dfs(R[pos]);
}
}
int jump (int a, int b) {
for (int i = 19; i >= 0; i--) {
if (b & (1 << i)) {
a = dp[i][a];
}
}
return a;
}
int lca (int a, int b) {
if (dep[a] > dep[b]) swap(a, b);
b = jump(b, dep[b] - dep[a]);
if (a == b) return a;
for (int i = 19; i >= 0; i--) {
int x = dp[i][a], y = dp[i][b];
if (x && y && x != y) {
a = x, b = y;
}
}
return dp[0][a];
}
vector <int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector<int> &a, const std::vector<int> &b) {
n = N;
vector <int> ret;
stack <int> cur;
for (int i = 1; i <= n; i++) {
deg[i] = (bits[2 * i - 2] == '1') + (bits[2 * i - 1] == '1');
}
cur.push(1);
for (int i = 2; i <= n; i++) {
while (!cur.empty()) {
if (deg[cur.top()] == 0) cur.pop();
else {
adj[cur.top()].push_back(i);
deg[cur.top()]--;
break;
}
}
cur.push(i);
}
for (int i = 1; i <= n; i++) {
L[i] = R[i] = -1;
sort(adj[i].begin(), adj[i].end());
bool f = 0;
if (bits[2 * i - 2] == '1') {
L[i] = adj[i][0]; f = 1;
}
if (bits[2 * i - 1] == '1') {
R[i] = (f ? adj[i][1] : adj[i][0]);
}
}
dfs2(1);
for (int i = 1; i <= n; i++) {
idx[inorder[i - 1]] = i;
}
for (int i = 1; i < 20; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = dp[i - 1][dp[i - 1][j]];
}
}
for (int i = 0; i < (int)a.size(); i++) {
ret.push_back(lca(idx[a[i]], idx[b[i]]));
}
return ret;
}
Compilation message
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 |
Incorrect |
2 ms |
7976 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
21 ms |
10784 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
57 ms |
16544 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
