Submission #647485

#	Time	Username	Problem	Language	Result	Execution time	Memory
647485		Matteo_Verz	Floppy (RMI20_floppy)	C++17	100 / 100	134 ms	19496 KiB

floppy

#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 (stderr)

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) {
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~

• Subtask 1: 7 / 7
• Subtask 2: 21 / 21
• Subtask 3: 72 / 72