Submission #1019472

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019472		spacewalker	Friend (IOI14_friend)	C++17	27 / 100	1038 ms	9776 KiB

friend

#include <bits/stdc++.h>

#include "friend.h"

using namespace std;

inline int connects_self(int p) {
  return p == 0 || p == 2;
}

inline int connects_neighbors(int p) {
  return p == 1 || p == 2;
}

// Find out best sample
int findSample(int n,int confidence[],int host[],int protocol[]){
  vector<vector<int>> children(n, vector<int>());
  for (int i = 1; i < n; ++i) children[host[i]].push_back(i);

  // first y/n: does there exist an indirect neighbor we picked
  // (path of neighbor-connects that goes up, then a direct connect,
  //  then the path goes back down through neighbor-connects)
  // second y/n: did we pick this node?
  // note that yy cannot happen; since the indirect neighbor and this node
  // are adjacent
  vector<int> best_nn(n), best_yn(n), best_ny(n);
  for (int i = n - 1; i >= 0; --i) {
    // We do some DP to account for the fact that a child might become
    // an indirect neighbor of another child's sibling.
    // maintain DP on suffixes of the list of children:
    // - max if we pick no neighbor-connected child
    //  - MUST pick yn if current child is neighbor-connected
    // - max if we picked some neighbor-connected child
    //  - MUST pick yn if current child is self-connected but not neighbor-contained
    //    then transition to next on some table
    //  - otherwise, can pick any (?)
    //
    // Aside from this, the 3 cases are:
    // best_nn: this DP runs as normal
    // best_yn: MUST pick yn if child connects_neighbors 
    // best_ny: MUST pick yn if child connects_self
    //
    // (these conditions being active are denoted by free_neighbor and free_self = false,
    // respectively)
    for (auto recurrence : {0, 1, 2}) { // nn, yn, ny
      vector<int> &table = (recurrence == 0 ? best_nn :
          (recurrence == 1 ? best_yn : best_ny));
      vector<int> no_neigh_connect(children.size() + 1), with_neigh_connect(children.size() + 1);
      bool free_neighbor = recurrence != 1;
      bool free_self = recurrence != 2;
      for (int k = (int)children[i].size() - 1; k >= 0; --k) {
        int v = children[i][k];
        auto must_yn = [&] (int v, bool free_neighbor, bool free_self) {
          bool must_yn = (!free_neighbor && connects_neighbors(protocol[v])) 
            || (!free_self && connects_self(protocol[v]));
          // cerr << "must yn " << must_yn << endl;
          return must_yn;
        };
        // update no_neigh_connect[k]
        if (must_yn(v, false, free_self)) {
          no_neigh_connect[k] = best_yn[v] + no_neigh_connect[k+1];
        } else {
          no_neigh_connect[k] = best_nn[v] + no_neigh_connect[k+1];
          if (!connects_neighbors(protocol[v])) {
            no_neigh_connect[k] = max(no_neigh_connect[k], best_ny[v] + no_neigh_connect[k+1]);
          }
        }
        // update with_neigh_connect[k]
        if (must_yn(v, free_neighbor, free_self) || (connects_self(protocol[v]) && !connects_neighbors(protocol[v]))) {
          with_neigh_connect[k] = best_yn[v] + with_neigh_connect[k+1];
        } else {
          with_neigh_connect[k] = best_nn[v] + with_neigh_connect[k+1];
          with_neigh_connect[k] = max(with_neigh_connect[k], best_ny[v] + with_neigh_connect[k+1]);
          if (connects_neighbors(protocol[v])) {
            with_neigh_connect[k] = max(with_neigh_connect[k], best_ny[v] + no_neigh_connect[k+1]);
          }
        }
        // cerr << "HN" << no_neigh_connect[k] << " " << with_neigh_connect[k] << endl;
      }
      if (children[i].size() > 0) {
        table[i] = max(no_neigh_connect[0], with_neigh_connect[0]);
        // cerr << "recc " << i << " " << recurrence << " " << table[i] << endl;
      }
    }
    best_ny[i] += confidence[i];
    // cerr << i << " values " << best_nn[i] << " " << best_yn[i] << " " << best_ny[i] << endl;
  }
  
  return max(best_nn[0], best_ny[0]);
}

• Subtask 1: 0 / 11
• Subtask 2: 8 / 8
• Subtask 3: 0 / 8
• Subtask 4: 19 / 19
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31