Submission #1221121

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221121		badge881	Floppy (RMI20_floppy)	C++20	100 / 100	64 ms	6256 KiB

floppy

#include <bits/stdc++.h>
#include "floppy.h"
using namespace std;

#define NMAX 100000
#define MMAX 100000

int leftc[NMAX], rightc[NMAX];
int par[18][NMAX], depth[NMAX];

int timer = 0;

void dfs_1(int u, const string &bits)
{
    if(bits[2*u] == '1')
    {
        int new_node = ++timer;
        par[0][new_node] = u;
        leftc[u] = new_node;
        depth[new_node] = depth[u]+1;
        dfs_1(new_node, bits);
    }
    if(bits[2*u+1] == '1')
    {
        int new_node = ++timer;
        par[0][new_node] = u;
        rightc[u] = new_node;
        depth[new_node] = depth[u]+1;
        dfs_1(new_node, bits);
    }
}

int jump(int a, int l)
{
    for(int i = 0; i < 18; i++)
        if((l&(1<<i)) != 0)
            a = par[i][a];
    return a;
}

int lca(int a, int b)
{
    if(depth[a] < depth[b])
        swap(a, b);
    a = jump(a, depth[a]-depth[b]);
    if(a == b)
        return a;
    
    for(int i = 17; i >= 0; i--)
        if(par[i][a] != par[i][b])
            a = par[i][a],
            b = par[i][b];
        
    return par[0][a];
}

int trans[NMAX], inv_trans[NMAX];

int code = 0;

void dfs_2(int u)
{
    if(leftc[u] != -1)
        dfs_2(leftc[u]);

    trans[u] = code;
    inv_trans[code] = u;
    code++;
    if(rightc[u] != -1)
        dfs_2(rightc[u]);
}


vector<int> solve_queries(int subtask_id, int n, const string &bits, const vector<int> &a, const vector<int> &b)
{
    for(int i = 0; i <= n; i++)
    {
        leftc[i] = -1;
        rightc[i] = -1;
        par[0][i] = -1;
    }
    dfs_1(0, bits);
    for(int i = 1; i <= 17; i++)
        for(int j = 0; j < n; j++)
            par[i][j] = par[i-1][par[i-1][j]];
        
    dfs_2(0);
    vector<int> answers;
    for(int i = 0; i < a.size(); i++)
    {
        answers.push_back(trans[lca(inv_trans[a[i]], inv_trans[b[i]])]);
    }
    return answers;
}

void read_array(int subtask_id, const vector<int> &v)
{
    int n = v.size();
    int rc[n], lc[n], p[n];
    for(int i = 0; i < n; i++)
    {
        rc[i] = -1;
        lc[i] = -1;
        p[i] = -1;
    }
    int root = 0;
    for(int i = 1; i < n; i++)
    {
        int last_val = i-1;
        while(last_val != -1)
        {
            if(-v[last_val] < -v[i])
            {
                lc[i] = rc[last_val];
                rc[last_val] = i;
                p[i] = last_val;
                p[lc[i]] = i;
                break;
            }
            last_val = p[last_val];
        }
        if(last_val == -1)
        {
            lc[i] = root;
            p[root] = i;
            root = i;
        }
    }
    string bits = "";
    stack<int> s;
    s.push(root);
    while(!s.empty())
    {
        int nw = s.top();
        s.pop();
        string bruh = "00";
        if(rc[nw] != -1)
        {
            bruh[1] = '1';
            s.push(rc[nw]);
        }
        if(lc[nw] != -1)
        {
            bruh[0] = '1';
            s.push(lc[nw]);
        }
        bits+=bruh;
    }
    save_to_floppy(bits);
}

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