# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1070824 |
2024-08-22T19:10:06 Z |
ASN49K |
Floppy (RMI20_floppy) |
C++14 |
|
71 ms |
16468 KB |
#include <bits/stdc++.h>
using namespace std;
#include "floppy.h"
const int UNSET=-1;
const int N=40'000;
const int LG=15;
int tt[LG+1][N],h[N];
int tin[N],tout[N];
int aux1,aux2;
void build(int n)
{
for(int i=1;i<=LG;i++)
{
for(int j=0;j<n;j++)
{
tt[i][j]=tt[i-1][tt[i-1][j]];
}
}
}
bool is_parent(int x,int y)
{
return (tin[x]<=tin[y] && tout[y]<=tout[x]);
}
int lca(int x,int y)
{
if(is_parent(x,y))return x;
if(is_parent(y,x))return y;
for(int i=LG;i>=0;i--)
{
if(!is_parent(tt[i][x] , y))
{
x=tt[i][x];
}
}
return tt[0][x];
}
void dfs(int nod,vector<int>&l,vector<int>&r,string& rez)
{
aux1++;
if(l[nod]!=UNSET)
{
rez[aux1<<1]='1';
}
if(r[nod]!=UNSET)
{
rez[aux1<<1|1]='1';
}
if(l[nod]!=UNSET)
{
dfs(l[nod] , l , r ,rez);
}
if(r[nod]!=UNSET)
{
dfs(r[nod] , l , r ,rez);
}
}
void read_array(int subtask_id, const std::vector<int> &v)
{
aux1=-1;
int n=(int)v.size();
string rez(2*n , '0');
vector<int>l(n,UNSET),r(n,UNSET);
stack<int>sk;
for(int i=0;i<n;i++)
{
while(sk.size() && v[sk.top()]<v[i])
{
l[i]=sk.top();
sk.pop();
}
sk.push(i);
}
while(sk.size())
{
sk.pop();
}
for(int i=n-1;i>=0;i--)
{
while(sk.size() && v[sk.top()]<v[i])
{
r[i]=sk.top();
sk.pop();
}
sk.push(i);
}
dfs(max_element(v.begin() , v.end()) - v.begin(),l,r,rez);
save_to_floppy(rez);
}
int dfs2(const string& bits)
{
int tinn=++aux1,l=UNSET,r=UNSET;
if(bits[tinn<<1]=='1')
{
l=dfs2(bits);
}
int nod=++aux2;
tin[nod]=tinn;
if(bits[tinn<<1|1]=='1')
{
r=dfs2(bits);
}
tout[nod]=aux1;
if(l!=UNSET)
{
tt[0][l]=nod;
}
if(r!=UNSET)
{
tt[0][r]=nod;
}
return nod;
}
std::vector<int> solve_queries(int subtask_id, int n,
const std::string &bits,
const std::vector<int> &a, const std::vector<int> &b){
int q=(int)a.size();
aux1=aux2=-1;
const int root=dfs2(bits);
tt[0][root]=root;
build(n);
vector<int>answers(q);
for(int i=0;i<q;i++)
{
answers[i]=lca(a[i] , b[i]);
}
return answers;
}
Compilation message
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) {
| ~~~~~~~~~~~~~~~~~~~~~^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
3108 KB |
Output is correct |
2 |
Correct |
1 ms |
2872 KB |
Output is correct |
3 |
Correct |
2 ms |
2876 KB |
Output is correct |
4 |
Correct |
2 ms |
2880 KB |
Output is correct |
5 |
Correct |
1 ms |
2872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
5576 KB |
Output is correct |
2 |
Correct |
15 ms |
5580 KB |
Output is correct |
3 |
Correct |
20 ms |
6016 KB |
Output is correct |
4 |
Correct |
19 ms |
5820 KB |
Output is correct |
5 |
Correct |
17 ms |
5564 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
14400 KB |
Output is correct |
2 |
Correct |
66 ms |
14508 KB |
Output is correct |
3 |
Correct |
71 ms |
16468 KB |
Output is correct |
4 |
Correct |
70 ms |
15668 KB |
Output is correct |
5 |
Correct |
65 ms |
14500 KB |
Output is correct |