제출 #1137188

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1137188		KhoaDuy	Floppy (RMI20_floppy)	C++20	59.27 / 100	75 ms	9732 KiB

floppy

#include "floppy.h"
#include<bits/stdc++.h>
using namespace std;
void encode(int u,vector<vector<int>> &graph,string &s){
    int cnt=graph[u].size();
    if(cnt==1&&u<graph[u][0]){
        cnt+=2;
    }
    s+=('0'+(cnt/2));
    s+=('0'+(cnt%2));
    for(int v:graph[u]){
        encode(v,graph,s);
    }
}
void read_array(int subtask_id,const vector<int> &v){
    int n=v.size();
    vector<vector<int>> graph(n);
    stack<int> st;
    int pa[n];
    for(int i=0;i<n;i++){
        pa[i]=-1;
        int last=-1;
        while(!st.empty()&&v[st.top()]<v[i]){
            last=st.top();
            st.pop();
        }
        if(!st.empty()){
            pa[i]=st.top();
        }
        if(last!=-1){
            pa[last]=i;
        }
        st.push(i);
    }
    int idx=0;
    for(int i=0;i<n;i++){
        if(pa[i]==-1){
            idx=i;
        }
        else{
            graph[pa[i]].push_back(i);
        }
    }
    string s="";
    encode(idx,graph,s);
    for(int i=0;i<n;i++){
        if(graph[i].size()==0){
            s+='1';
        }
        else{
            s+='0';
        }
    }
    save_to_floppy(s);
}
void decode(int u,int &tim,vector<int> &leaf,int le[],int ri[],int idx[],int pa[],const string &bits,int depth[]){
    int childcnt=2*(bits[2*u]-'0')+bits[2*u+1]-'0';
    if(childcnt==0){
        idx[u]=leaf.back();
        leaf.pop_back();
        le[u]=idx[u];
        ri[u]=idx[u];
    }
    else if(childcnt==1||childcnt==3){
        tim++;
        int v=tim;
        depth[v]=depth[u]+1;
        decode(v,tim,leaf,le,ri,idx,pa,bits,depth);
        if(childcnt==1){
            le[u]=le[v];
            ri[u]=ri[v]+1;
            idx[u]=ri[u];
        }
        else{
            le[u]=le[v]-1;
            ri[u]=ri[v];
            idx[u]=le[u];
        }
        pa[idx[v]]=idx[u];
    }
    else{
        int vle,vri;
        tim++;
        vle=tim;
        depth[vle]=depth[u]+1;
        decode(vle,tim,leaf,le,ri,idx,pa,bits,depth);
        tim++;
        vri=tim;
        depth[vri]=depth[u]+1;
        decode(vri,tim,leaf,le,ri,idx,pa,bits,depth);
        le[u]=le[vle];
        ri[u]=ri[vri];
        assert(ri[vle]+2==le[vri]);
        idx[u]=ri[vle]+1;
        pa[idx[vle]]=idx[u];
        pa[idx[vri]]=idx[u];
    }
}
vector<int> solve_queries(int subtask_id,int n,const string &bits,const vector<int> &l,const vector<int> &r){
    assert(bits.length()==3*n);
    int le[n],ri[n],idx[n];
    int lift[17][n];
    int depth[n];
    int tim=0;
    vector<int> leaf;
    for(int i=2*n;i<3*n;i++){
        if(bits[i]=='1'){
            leaf.push_back(i-2*n);
        }
    }
    depth[0]=0;
    reverse(leaf.begin(),leaf.end());
    decode(0,tim,leaf,le,ri,idx,lift[0],bits,depth);
    lift[0][idx[0]]=idx[0];
    int nxt[n];
    for(int i=0;i<n;i++){
        nxt[idx[i]]=depth[i];
    }
    for(int i=0;i<n;i++){
        depth[i]=nxt[i];
    }
    for(int i=1;i<17;i++){
        for(int j=0;j<n;j++){
            lift[i][j]=lift[i-1][lift[i-1][j]];
        }
    }
    vector<int> ans;
    for(int j=0;j<l.size();j++){
        int u=l[j],v=r[j];
        if(depth[u]<depth[v]){
            swap(u,v);
        }
        for(int i=16;i>=0;i--){
            if((depth[u]-depth[v])&(1<<i)){
                u=lift[i][u];
            }
        }
        if(u==v){
            ans.push_back(u);
            continue;
        }
        for(int i=16;i>=0;i--){
            if(lift[i][u]!=lift[i][v]){
                u=lift[i][u],v=lift[i][v];
            }
        }
        ans.push_back(lift[0][u]);
    }
    return ans;
}

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