Submission #1136451

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136451		nathan4690	Floppy (RMI20_floppy)	C++20	100 / 100	64 ms	8640 KiB

floppy

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

int n, le[40005], ri[40005], par[16][40005], lc[40005], rc[40005];
vector<int> G[40005];
string res, s;

void findTour(int u){
    res += '0' + (lc[u] != -1);
    res += '0' + (rc[u] != -1);
    for(int c: G[u]) findTour(c);
}

void read_array(int subtask_id, const std::vector<int> &v) {
    n = v.size();
    vector<int> S;
    for(int i=0;i<n;i++){
        lc[i] = rc[i] = -1;
        while(!S.empty()){
            int x = S.back();
            if(v[x] < v[i]) S.pop_back();
            else break;
        }
        if(S.empty()){
            le[i] = -1;
        }else le[i] = S.back();
        S.push_back(i);
    }
    S.clear();
    for(int i=n-1;i>=0;i--){
        while(!S.empty()){
            int x = S.back();
            if(v[x] < v[i]) S.pop_back();
            else break;
        }
        if(S.empty()){
            ri[i] = -1;
        }else ri[i] = S.back();
        S.push_back(i);
    }
    int root = 0;
    for(int i=0;i<n;i++){
        int p = -1;
        bool isLeft = true;
        if(le[i] == -1) {
            p = ri[i];
            isLeft = 1;
        }else if(ri[i] == -1) {
            p = le[i];
            isLeft = 0;
        }else{
            if(v[le[i]] < v[ri[i]]) {
                p = le[i];
                isLeft = 0;
            }else {
                p = ri[i];
                isLeft = 1;
            }
        }
        if(p == -1) {
            root = i;
            continue;
        }
        if(isLeft) lc[p] = i;
        else rc[p] = i;
        G[p].push_back(i);
    }
//    for(int i=0;i<n;i++) {
////        cout << idn[i] << " = " << i << endl;
//        for(int c: G[i]){
//            cout << i << " -> " << c << endl;
//        }
//    }
    findTour(root);
    save_to_floppy(res);
}

int cu, idn[40005], cornode[40005], depth[40005];

pair<int,int> getTour(int sp, int ss){
//    cout << sp << ' ' << ss << endl;
//    cout << u << endl;
//    cout << u << " (" << le[u] << ", " << ri[u] << ")" << endl;
    int u = cu++;
    idn[u] = sp;
    int ssn = ss + 2;
    pair<int,int> rr = {idn[u], ssn};
    if(s[ss] == '1'){
//        cout << u << " --> " << cu << endl;
        G[u].push_back(cu);
        depth[cu] = depth[u] + 1;
        par[0][cu] = u;
        rr = getTour(sp, ssn);
        idn[u] = rr.first;
        ssn = rr.second;
    }
    if(s[ss+1] == '1'){
//        cout << u << " --> " << cu << endl;
        G[u].push_back(cu);
        depth[cu] = depth[u] + 1;
        par[0][cu] = u;
        rr = getTour(idn[u] + 1, ssn);
    }else rr.first++;
//    cout << u << ' ' << s[ss] << s[ss+1] << ' ' << idn[u] << endl;
    return rr;
}

int LCA(int u, int v){
    if(depth[u] > depth[v]) swap(u, v);
    int l = depth[v] - depth[u];
    for(int i=0;i<16;i++){
        if(l & (1 << i)) v = par[i][v];
    }
    if(u == v) return u;
    for(int i=15;i>=0;i--){
        if(par[i][u] != par[i][v]){
            u = par[i][u];
            v = par[i][v];
        }
    }
    return par[0][u];
}

std::vector<int> solve_queries(int subtask_id, int N,
        const std::string &bits,
        const std::vector<int> &a, const std::vector<int> &b) {
//    cout << bits << endl;
    for(int i=0;i<N;i++) G[i].clear();
    s = bits;
    cu = 0;
    getTour(0, 0);
    for(int i=0;i<N;i++){
        for(int x=1;x<16;x++){
            par[x][i] = par[x-1][par[x-1][i]];
        }
    }

//    for(int i=0;i<N;i++) {
////        cout << idn[i] << " = " << i << endl;
//        for(int c: G[i]){
//            cout << i << " --> " << c << endl;
//        }
//    }
    for(int i=0;i<N;i++) {
//        cout << idn[i] << " = " << i << endl;
//        cout << "! " << i << ' ' << idn[i] << endl;
        cornode[idn[i]] = i;
    }
    vector<int> answers;
    for(int i=0;i<a.size();i++){
        int u = cornode[a[i]], v = cornode[b[i]];
//        cout << "? " << a[i] << ' ' << b[i] << ' ' << u << ' ' << v << ' ' << LCA(u, v) << ' ' << idn[LCA(u, v)] << endl;
        answers.push_back(idn[LCA(u, v)]);
    }
    return answers;
}

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