oj.uz

Submission #642872

# Submission time Handle Problem Language Result Execution time Memory
642872 2022-09-20T17:17:24 Z lis05st Floppy (RMI20_floppy) C++17
0 / 100
 607 ms 262144 KB 
#include <stdlib.h>
#include <string.h>

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

const int NMAX=4e4;
int ARR[NMAX+5],L[NMAX+5],R[NMAX+5],pr[NMAX+5];

string floppy;
vector<int>vec;
void dfs(int v){
    floppy+='0'+(L[v]==-1?0:1);
    floppy+='0'+(R[v]==-1?0:1);
    if(L[v]!=-1)dfs(L[v]);
    vec.push_back(ARR[v]);
    if(R[v]!=-1)dfs(R[v]);
}

int sL[NMAX+5],sR[NMAX+5],spr[20][NMAX+5];
int TIME=1,ID=0;
vector<int>arr;
int dfs2(string&s){
    bool haveLeft=s[ID]=='1';
    bool haveRight=s[ID+1]=='1';
    ID+=2;
    if(haveLeft){
        int x=dfs2(s);
        sL[TIME]=x;
        spr[0][x]=TIME;
    }
    int v=TIME;
    arr.push_back(v);
    spr[0][v]=v;
    TIME++;
    if(haveRight){
        int x=dfs2(s);
        sR[v]=x;
        spr[0][x]=v;
    }
    return v;
}
int tin[NMAX+5],tout[NMAX+5];
int T=0;
int depth[NMAX+5];
void dfs3(int v,int d){
    if(v==-1)return;
    tin[v]=++T;
    for(int lvl=1;lvl<=19;lvl++)spr[lvl][v]=spr[lvl-1][spr[lvl-1][v]];
    depth[v]=d;
    dfs3(L[v],d+1);
    dfs3(R[v],d+1);
    tout[v]=++T;
}

int restore(string s){
    memset(sL,-1,sizeof sL);
    memset(sR,-1,sizeof sR);
    int root=dfs2(s);
    return root;
}

bool aprofb(int a,int b){
    if(tin[a]<=tin[b]&&tout[b]<=tout[a])return 1;
    return 0;
}

int lca(int a,int b){
    if(a==b)return a;
    //cout<<"LCA "<<a<<" "<<b<<"\n";
    for(int lvl=19;lvl>=0;lvl--){
        //cout<<lvl<<" "<<a<<" "<<b<<"\n";
        if(depth[a]<depth[b])swap(a,b);
        //cout<<spr[lvl][a]<<"\n";
        if(!aprofb(spr[lvl][a],b))a=spr[lvl][a];
    }
    if(depth[a]<depth[b])swap(a,b);
    return spr[0][a];
}

void read_array(int subtask_id, const std::vector<int> &v) {
    map<int,int>mp;
    vector<int>vec2;
    vector<int>v2=v;
    for(auto e:v)vec2.push_back(e);
    sort(vec2.begin(),vec2.end());
    for(int i=0;i<v.size();i++)mp[vec2[i]]=i;
    for(auto&e:v2)e=mp[e];
    int n=v.size();
    for(int i=1;i<=n;i++)ARR[i]=v2[i-1];

    int root=1;
    L[root]=-1;
    R[root]=-1;
    pr[root]=-1;
    for(int i=2;i<=n;i++){
        L[i]=R[i]=-1;
        int last=i-1;
        while(last!=root&&ARR[last]<ARR[i])last=pr[last];
        if(ARR[last]<ARR[i]){
            root=i;
            L[i]=last;
            pr[last]=i;
        }
        else if(R[last]==-1){
            R[last]=i;
            pr[i]=last;
        }else{
            pr[i]=last;
            pr[R[last]]=i;
            L[i]=R[last];
            R[last]=i;
        }
    }
    dfs(root);
    save_to_floppy(floppy);
}

std::vector<int> solve_queries(int subtask_id, int N,
        const std::string &bits,
        const std::vector<int> &a, const std::vector<int> &b) {
    string ss=bits;
    int root=restore(ss);
    //cout<<root<<"\n";
    dfs3(root,0);
    int n=bits.size()/2;
    std::vector<int> answers = vector<int>(N,0);
    for(int i=0;i<a.size();i++)answers[i]=lca(a[i]+1,b[i]+1)-1;
    return answers;
}

Compilation message

floppy.cpp: In function 'void read_array(int, const std::vector<int>&)':
floppy.cpp:88:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for(int i=0;i<v.size();i++)mp[vec2[i]]=i;
      |                 ~^~~~~~~~~
floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:129:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |     for(int i=0;i<a.size();i++)answers[i]=lca(a[i]+1,b[i]+1)-1;
      |                 ~^~~~~~~~~
floppy.cpp:127:9: warning: unused variable 'n' [-Wunused-variable]
  127 |     int n=bits.size()/2;
      |         ^
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
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 518 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 551 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 72.0

# Verdict Execution time Memory Grader output
1 Runtime error 607 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -