Submission #1067175

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067175		juicy	Snowy Roads (JOI16_snowy)	C++17	100 / 100	12 ms	1980 KiB

Anya

#include "Anyalib.h"

#include <bits/stdc++.h>

using namespace std;

namespace {
  const int N = 500;
  
  int n;
  int pr[N], c[N];
  vector<int> cands;
  vector<array<int, 2>> g[N];

  int dfs(int u) {
    int cur = 0;
    for (auto [v, i] : g[u]) {
      if (v != pr[u]) {
        pr[v] = u;
        cur = max(cur, dfs(v));
      }
    }
    if (cur == 11) {
      cands.push_back(u);
      cur = 0;
    }
    return cur + 1;
  }

  void color(int u, int *C) {
    for (auto [v, i] : g[u]) {
      if (v != pr[u]) {
        Save(v, C[i]);
        c[v] = c[u] + C[i];
        color(v, C);
      }
    }
  }
}

void InitAnya(int N, int *A, int *B) {
  n = N;
  for (int i = 0; i < N - 1; ++i) {
    g[A[i]].push_back({B[i], i});
    g[B[i]].push_back({A[i], i});
  }
  dfs(0);
}

void Anya(int *C) {
  c[0] = 0;
  color(0, C);
  for (int i = 0; i < cands.size(); ++i) {
    for (int j = 0; j < 9; ++j) {
      Save(500 + i * 9 + j, c[cands[i]] >> j & 1);
    } 
  }
}

Boris

#include "Borislib.h"

#include <bits/stdc++.h>

using namespace std;

namespace {
  const int N = 500;
  
  int n, p = 0;
  int pr[N], spec[N];
  vector<int> g[N];

  int dfs(int u) {
    int cur = 0;
    for (int v : g[u]) {
      if (v != pr[u]) {
        pr[v] = u;
        cur = max(cur, dfs(v));
      }
    }
    if (cur == 11) {
      spec[u] = ++p; 
      cur = 0;
    }
    return cur + 1;
  }
}


void InitBoris(int N, int *A, int *B) {
  n = N;
  for (int i = 0; i < N - 1; ++i) {
    g[A[i]].push_back(B[i]);
    g[B[i]].push_back(A[i]);
  }
  pr[0] = -1;
  dfs(0);
}

int Boris(int u) {
  int res = 0;
  while (~u && !spec[u]) {
    res += Ask(u);
    u = pr[u];
  }
  if (spec[u]) {
    for (int j = 0; j < 9; ++j) {
      res += Ask(500 + 9 * (spec[u] - 1) + j) << j;
    }
  }
  return res;
}

Compilation message (stderr)

Anya.cpp: In function 'void Anya(int*)':
Anya.cpp:53:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for (int i = 0; i < cands.size(); ++i) {
      |                   ~~^~~~~~~~~~~~~~

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