oj.uz

Submission #492537

# Submission time Handle Problem Language Result Execution time Memory
492537 2021-12-07T18:21:08 Z cadmiumsky Floppy (RMI20_floppy) C++14
100 / 100
 115 ms 17916 KB 
#include <stdlib.h>
#include <string.h>
#include <stack>
#include <iostream>

#include "floppy.h"

using namespace std;

void read_array(int subtask_id, const std::vector<int> &v) {
  string bits="";
  stack<int> st;
  for(int i=0; i<v.size(); i++) {
    while(!st.empty() && st.top()<v[i]) {
      st.pop();
      bits+="1";
    }
    if(v.size()!=i+1)
      bits+="0";
    st.push(v[i]);
  }
  save_to_floppy(bits);
}

int father[40000][16];
vector<int> tree[40000];
int pin[40000];
int pout[40000];
int inp;
static void dfs(int x) {
  pin[x]=inp++;
  for(auto y:tree[x])
    dfs(y);
  pout[x]=inp-1;
}

static bool isanc(int x, int y) {
  return pin[x]<=pin[y] && pout[x]>=pout[y];
}
static int lca(int x, int y) {
  if(isanc(x,y))
    return x;
  if(isanc(x,y))
    return y;
  for(int i=15; i>=0; i--) {
    if(!isanc(father[x][i],y))
      x=father[x][i];
  }
  return father[x][0];
}

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 << '\n';
  stack<int> st;
  vector<int> ans;
  int ptr=0;
  for(int i=0,last; i<n; i++) {
    last=-1;
    while(ptr<bits.size() && bits[ptr]=='1') {
      last=st.top();
      st.pop();
      ptr++;
    }
    if(last!=-1)
      father[last][0]=i;
    last=-1;
    if(st.size())
      last=st.top();
    father[i][0]=last;
    st.push(i);
    ptr++;
  }
  int root=0;
  for(int i=0; i<n; i++) {
    //cout << father[i][0] <<' ';
    if(father[i][0]==-1)
      root=i;
    else
      tree[father[i][0]].push_back(i);
  }
  //cout << '\n';
  dfs(root);
  father[root][0]=root;
  for(int step=1; step<16; step++) {
    for(int i=0; i<n; i++)
      father[i][step]=father[father[i][step-1]][step-1];
  }
  for(int i=0; i<a.size(); i++) {
    ans.push_back(lca(a[i],b[i]));
  }
  return ans;
}

Compilation message

floppy.cpp: In function 'void read_array(int, const std::vector<int>&)':
floppy.cpp:13:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |   for(int i=0; i<v.size(); i++) {
      |                ~^~~~~~~~~
floppy.cpp:18:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   18 |     if(v.size()!=i+1)
      |        ~~~~~~~~^~~~~
floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:61:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     while(ptr<bits.size() && bits[ptr]=='1') {
      |           ~~~^~~~~~~~~~~~
floppy.cpp:90:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |   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 3 ms 2560 KB Output is correct
2 Correct 3 ms 2560 KB Output is correct
3 Correct 2 ms 2572 KB Output is correct
4 Correct 2 ms 2572 KB Output is correct
5 Correct 2 ms 2572 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 5280 KB Output is correct
2 Correct 22 ms 5376 KB Output is correct
3 Correct 20 ms 5464 KB Output is correct
4 Correct 25 ms 5524 KB Output is correct
5 Correct 26 ms 5128 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 13500 KB Output is correct
2 Correct 115 ms 13528 KB Output is correct
3 Correct 89 ms 17916 KB Output is correct
4 Correct 93 ms 17376 KB Output is correct
5 Correct 95 ms 17020 KB Output is correct