Submission #572014

#	Time	Username	Problem	Language	Result	Execution time	Memory
572014		cadmiumsky	Park (JOI17_park)	C++14	0 / 100	56 ms	17924 KiB

park

#include "park.h"
#include <bits/stdc++.h>
using namespace std;
using vectorit = vector<int>::iterator;
using pii = pair<int,int>;
const int nmax = 14e2 + 5;
int n;
int lg[nmax];

namespace Query {
  int Place[nmax];
  bool query(int s, int t, vectorit l, vectorit r) {
    for(int i = 0; i < n; i++)
      Place[i] = 0;
    while(l != r)
      Place[*l] = 1,
      l++;
    Place[s] = 1;
    Place[t] = 1;
    if(s > t)
      swap(s, t);
    return Ask(s, t, Place);
  }
  bool query(int s, int t, vector<int> v) {
    return query(s, t, v.begin(), v.end());
  }
};
using namespace Query;

class Tree {
  vector< vector<int> > t;
  public:
    int root;
    vector<int> preord;
    vector<pii> edg;
    unordered_set<int> V;
    void addedge(int x, int y) { 
      V.insert(x), V.insert(y);
      t[x].push_back(y), t[y].push_back(x); 
    }
    void dfspreord(int node, int f) {
      preord.push_back(node);
      for(auto x : t[node]) {
        if(x == f)
          continue;
        dfspreord(x, node);
      }
      return;
    }
    void dfspreord() {preord.clear(); dfspreord(root, root); }
    vector<Tree> decompound(int elim) {
      vector<Tree> rez;
      function<void(int,int)> push = [&](int node, int f) {
        if(node != f)
          rez.back().addedge(node, f);
        for(auto x : t[node])
          if(x != f && x != elim)
            push(x, node);
        return;
      };
      for(auto x : t[elim]) {
        rez.push_back(Tree(t.size(), x));
        push(x, x);
        rez.back().dfspreord();
      }
      return rez;
    }
    int binsearch(int aux) {
      if(query(aux, preord[0], preord.begin(), preord.begin()))
        return preord[0];
      int lim = 0, temp;
      for(int i = lg[preord.size()]; i >= 0; i--) {
        temp = min((int)preord.size(), lim + (1 << i));
        if(!query(aux, preord[0], preord.begin(), preord.begin() + temp))
          lim = temp;
      }
      while(!(lim < preord.size()));
      return preord[lim];
    }
    ~Tree() {
      preord.clear();
      t.clear();
    }
    Tree(int len = n, int rt = 0) {
      t.clear();
      preord.clear();
      t.resize(len);
      V.insert(rt);
      root = rt;
    }
};
vector<pii> edg;

vector<Tree> trees;
void add(int node) {
  vector<int> pivots, cpy;
  vector<Tree> st;
  for(int i = 0; i < trees.size(); i++) { // identifying newly connected components
    Tree& t = trees[i];
    if(query(node, t.root, t.preord))
      st.push_back(t),
      swap(trees.back(), t),
      pivots.push_back(t.binsearch(node)),
      trees.pop_back();
  }
  if(st.empty()) { // if there are none, continue
    trees.push_back(Tree(n, node));
    trees.back().dfspreord();
    return;
  }
  
  for(auto a : pivots)
    edg.emplace_back(a, node);
  
  cpy = pivots;
  st[0].addedge(pivots[0], node);
  
  while(st.size() > 1) { // merging all components tied to node
    auto& t = st.back();
    for(auto [a, b] : t.edg)
      st[0].addedge(a, b);
    st[0].addedge(node, pivots.back());
    st.pop_back();
    pivots.pop_back();
  }
  st.back().dfspreord();
  trees.push_back(st[0]); // adding it to the legitimate list
  pivots = move(cpy);
  
  auto tempst = st[0].decompound(node);
  st.clear();
  
  for(auto t : tempst) { // continuing the reduction
    int val = -1;
    for(int i = 0; i < pivots.size(); i++)
      if(t.V.count(pivots[i])) {
        val = pivots[i];
        swap(pivots.back(), pivots[i]);
        pivots.pop_back();
        break;
      }
    while(!(val != -1));
    auto tempt = t.decompound(val);
    copy(tempt.begin(), tempt.end(), back_inserter(st));
    tempt.clear();
  }
  tempst.clear();
  
  while(!st.empty()) { // finding all edges within forest
    if(!query(node, st.back().root, st.back().preord)) {
      st.pop_back();
      continue;
    }
    int aux = st.back().binsearch(node);
    edg.emplace_back(aux, node);
    auto t = st.back();
    st.pop_back();
    auto vt = t.decompound(aux);
    copy(vt.begin(), vt.end(), back_inserter(st));
    vt.clear();
  }
}

void Detect(int T, int N) {
	n = N;
  lg[1] = 0;
  for(int i = 2; i <= n; i++) 
    lg[i] = lg[i >> 1] + 1;
  for(int i = 0; i < n; i++)
    add(i);
  for(auto [a, b] : edg) {
    if(a > b)
      swap(a, b);
    //cerr << a << ' ' << b << '\n';
    Answer(a, b);
  }
  return;
}

Compilation message (stderr)

park.cpp: In member function 'int Tree::binsearch(int)':
park.cpp:77:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |       while(!(lim < preord.size()));
      |               ~~~~^~~~~~~~~~~~~~~
park.cpp: In function 'void add(int)':
park.cpp:98:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Tree>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |   for(int i = 0; i < trees.size(); i++) { // identifying newly connected components
      |                  ~~^~~~~~~~~~~~~~
park.cpp:120:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  120 |     for(auto [a, b] : t.edg)
      |              ^
park.cpp:135:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     for(int i = 0; i < pivots.size(); i++)
      |                    ~~^~~~~~~~~~~~~~~
park.cpp: In function 'void Detect(int, int)':
park.cpp:171:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  171 |   for(auto [a, b] : edg) {
      |            ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 27
• Subtask 4: 0 / 30
• Subtask 5: 0 / 23