Submission #213129

#	Time	Username	Problem	Language	Result	Execution time	Memory
213129		EntityIT	Snowy Roads (JOI16_snowy)	C++14	100 / 100	31 ms	2156 KiB

Anya

#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

#include "Anyalib.h"

namespace {
  inline int nxt(int i, int n) { return i == n - 1 ? 0 : i + 1; }
  inline int prv(int i, int n) { return !i ? n - 1 : i - 1; }

  int n;
  vector<vector<pair<int, int> > > gr;

  vector<int> group;
  array<int, 10> nEle;
  void dfs(int u, int pr, int iGroup) {
    group[u] = iGroup;
    ++nEle[iGroup];
    for (const auto &v : gr[u]) if (v.first ^ pr) dfs(v.first, u, nxt(iGroup, 10) );
  }

  int mnGroup;

  vector<int> pos;
}

void InitAnya(int N, int A[], int B[]) {
  n = N;
  gr.assign(n, {} );
  for (int i = 0; i < n - 1; ++i) {
    gr[ A[i] ].emplace_back(B[i], i);
    gr[ B[i] ].emplace_back(A[i], i);
  }

  group.assign(n, -1);
  fill(all(nEle), 0);
  dfs(0, -1, 0);

  mnGroup = (int)(min_element(all(nEle) ) - nEle.begin() );

  pos.assign(n, -1);
  for (int u = 0, curPos = 0; u < n; curPos += group[u] ^ mnGroup ? 1 : 9, ++u) pos[u] = curPos;
}

void Anya(int C[]) {
  function<void(int, int, int, int)> setBit = [&](int u, int pr, int cur, int prv) {
    if (u) {
      if (group[u] ^ mnGroup) Save(pos[u], prv);
      else {
        for (int i = 0; i < 9; ++i) Save(pos[u] + i, cur >> i & 1);
      }
    }
    for (const auto &v : gr[u]) if (v.first ^ pr) setBit(v.first, u, cur + C[v.second], C[v.second]);
  };
  setBit(0, -1, 0, -1);
}

Boris

#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

#include "Borislib.h"

namespace {
  inline int nxt(int i, int n) { return i == n - 1 ? 0 : i + 1; }
  inline int prv(int i, int n) { return !i ? n - 1 : i - 1; }

  int n;
  vector<vector<pair<int, int> > > gr;

  vector<int> group, par;
  array<int, 10> nEle;
  void dfs(int u, int pr, int iGroup) {
    group[u] = iGroup;
    par[u] = pr;
    ++nEle[iGroup];
    for (const auto &v : gr[u]) if (v.first ^ pr) dfs(v.first, u, nxt(iGroup, 10) );
  }

  int mnGroup;

  vector<int> pos;
}

void InitBoris(int N , int A[] , int B[]) {
  n = N;
  gr.assign(n, {} );
  for (int i = 0; i < n - 1; ++i) {
    gr[ A[i] ].emplace_back(B[i], i);
    gr[ B[i] ].emplace_back(A[i], i);
  }

  group.assign(n, -1);
  par.assign(n, -1);
  fill(all(nEle), 0);
  dfs(0, -1, 0);

  mnGroup = (int)(min_element(all(nEle) ) - nEle.begin() );

  pos.assign(n, -1);
  for (int u = 0, curPos = 0; u < n; curPos += group[u] ^ mnGroup ? 1 : 9, ++u) pos[u] = curPos;
}

int Boris(int city) {
  int ret = 0;
  for (; city && group[city] ^ mnGroup; city = par[city]) ret += Ask(pos[city]);
  if (city) {
    for (int i = 0; i < 9; ++i) if (Ask(pos[city] + i) ) ret += 1 << i;
  }

  return ret;
}

• Subtask 1: 15 / 15
• Subtask 2: 5 / 5
• Subtask 3: 35 / 35
• Subtask 4: 45 / 45