oj.uz

Submission #1057013

# Submission time Handle Problem Language Result Execution time Memory
1057013 2024-08-13T13:15:11 Z ssense Floppy (RMI20_floppy) C++14
100 / 100
 52 ms 17664 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include "floppy.h"
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <limits.h>
#include <cassert>
 
#define fr first
#define sc second
 
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)
{
    //cout << "AT NODE " << u << endl;
    if(bits[2*u] == '1')
    {
        int new_node = ++timer;
        par[0][new_node] = u;
        leftc[u] = new_node;
        depth[new_node] = depth[u]+1;
        //cout << "GO TO NODE " << new_node << endl;
        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;
        //cout << "GO TO NODE " << new_node << endl;
        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;
    }
    //cout << bits << endl;
    save_to_floppy(bits);
}

 
/*
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
11 5
21 27 23 29 22 18 20 10 15 12 25
0 2 1
2 6 3
0 10 3
7 9 8
7 7 7
*/
 
/*
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <cassert>
*/

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:130:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |     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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9000 KB Output is correct
2 Correct 1 ms 9008 KB Output is correct
3 Correct 2 ms 9008 KB Output is correct
4 Correct 2 ms 9000 KB Output is correct
5 Correct 1 ms 9000 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 11052 KB Output is correct
2 Correct 13 ms 11052 KB Output is correct
3 Correct 12 ms 11176 KB Output is correct
4 Correct 13 ms 11328 KB Output is correct
5 Correct 12 ms 11056 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 17208 KB Output is correct
2 Correct 50 ms 17284 KB Output is correct
3 Correct 50 ms 17144 KB Output is correct
4 Correct 52 ms 17664 KB Output is correct
5 Correct 49 ms 17128 KB Output is correct