Submission #484919

#	Time	Username	Problem	Language	Result	Execution time	Memory
484919		blue	Floppy (RMI20_floppy)	C++17	100 / 100	172 ms	30184 KiB

floppy

#include <stdlib.h>
#include <string.h>
#include "floppy.h"
#include <vector>
#include <iostream>
#include <queue>
#include <stack>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;

const int INF = 1'000'000'001;
const int maxN = 40'000;
const int logN = 16;

vi V(maxN+1, INF);
vi lft(maxN, maxN);
vi rgt(maxN, maxN);
vi parent(maxN, maxN);
vvi children(maxN);

string ans;

void dfs(int u)
{
    if(children[u].empty())
    {
        ans.push_back('0');
        ans.push_back('0');
    }
    else if(int(children[u].size()) == 1)
    {
        if(children[u][0] < u)
        {
            ans.push_back('1');
            ans.push_back('0');
        }
        else
        {
            ans.push_back('0');
            ans.push_back('1');
        }
    }
    else
    {
        ans.push_back('1');
        ans.push_back('1');
    }
    // ans.push_back('0');
    for(int v: children[u]) dfs(v);
    // ans.push_back('1');
}

void read_array(int subtask_id, const std::vector<int> &v)
{
    int N = int(v.size());
    for(int i = 0; i < N; i++) V[i] = v[i];

    vi s(1, N);

    for(int i = 0; i < N; i++)
    {
        while(V[s.back()] < V[i]) s.pop_back();
        lft[i] = s.back();

        s.push_back(i);
    }

    s = vi(1, N);

    for(int i = N-1; i >= 0; i--)
    {
        while(V[s.back()] < V[i]) s.pop_back();
        rgt[i] = s.back();

        s.push_back(i);
    }

    // for(int i = 0; i < N; i++) cerr << i << " : " << lft[i] << ' ' << rgt[i] << '\n';

    int rt;

    for(int i = 0; i < N; i++)
    {
        parent[i] = (V[lft[i]] < V[rgt[i]] ? lft[i] : rgt[i]);
        if(parent[i] == N)
            rt = i;
        else
            children[parent[i]].push_back(i);
    }

    // cerr << "rt = " << rt << '\n';

    dfs(rt);

    // cerr << "returning " << ans << '\n';

    save_to_floppy(ans);
    //
    // std::string bits = "001100";
    // save_to_floppy(bits);
}






vvi dfs_children(maxN);

string bits;

vi solve_parent(maxN, -1);
vvi solve_children(maxN+1);
// vi act_parent(maxN, 0);

vi actual_index(maxN);

int ct = -1;
int d = 0;

vvi anc(maxN+1, vi(1+logN, maxN));
vi depth(maxN, 0);




void solve_dfs(int u)
{
    // cerr << "solve dfs " << u << " with d = " << d << '\n';
    int d1 = d;

    if(bits[2*u] == '1')
    {
        d++;
        solve_parent[d] = u;
        solve_dfs(d);
    }

    ct++;
    actual_index[u] = ct;

    // cerr << "actual index " << u << " = " << ct << '\n';

    if(bits[2*u+1] == '1')
    {
        d++;
        solve_parent[d] = u;
        solve_dfs(d);
    }
}

int lca(int u, int v)
{
    if(depth[u] > depth[v]) swap(u, v);
    for(int e = logN; e >= 0; e--)
    {
        if(depth[v] - (1 << e) < depth[u]) continue;
        v = anc[v][e];
    }

    if(u == v) return u;

    for(int e = logN; e >= 0; e--)
    {
        if(anc[u][e] != anc[v][e])
        {
            u = anc[u][e];
            v = anc[v][e];
        }
    }

    return anc[u][0];
}

std::vector<int> solve_queries(int subtask_id, int N,
        const std::string &bits_,
        const std::vector<int> &a, const std::vector<int> &b) {

    bits = bits_;
    solve_dfs(0);
    // solve_dfs2(0);

    // for(int i = 0; i < N; i++) cerr << solve_parent[i] << '\n';

    for(int i = 0; i < N; i++)
    {
        if(solve_parent[i] == -1) continue;
        anc[ actual_index[i] ][0] = actual_index[ solve_parent[i] ];
    }

    for(int i = 0; i < N; i++) if(anc[i][0] == maxN) anc[i][0] = N;
    anc[N][0] = N;

    for(int i = 0; i < N; i++) solve_children[anc[i][0]].push_back(i);

    queue<int> tbv;
    tbv.push(N);
    while(!tbv.empty())
    {
        int u = tbv.front();
        tbv.pop();

        for(int v: solve_children[u])
        {
            depth[v] = depth[u] + 1;
            tbv.push(v);
        }
    }

    // for(int i = 0; i <= N; i++) cerr << i << " : " << anc[i][0] << ' ' << depth[i] << "\n";
    // cerr << '\n';

    for(int e = 1; e <= logN; e++)
        for(int i = 0; i <= N; i++)
            anc[i][e] = anc[ anc[i][e-1] ][e-1];

    // return answers;

    vi answers(int(a.size()));
    for(int j = 0; j < int(a.size()); j++) answers[j] = lca(a[j], b[j]);
    return answers;
}

Compilation message (stderr)

floppy.cpp: In function 'void solve_dfs(int)':
floppy.cpp:132:9: warning: unused variable 'd1' [-Wunused-variable]
  132 |     int d1 = d;
      |         ^~
floppy.cpp: In function 'void read_array(int, const std::vector<int>&)':
floppy.cpp:95:8: warning: 'rt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   95 |     dfs(rt);
      |     ~~~^~~~
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