Submission #283031

#	Time	Username	Problem	Language	Result	Execution time	Memory
283031		rama_pang	Snowy Roads (JOI16_snowy)	C++14	100 / 100	63 ms	2644 KiB

Anya

#include "Anyalib.h"
#include <bits/stdc++.h>
using namespace std;

namespace {

int N;
vector<int> A, B;
map<pair<int, int>, int> name;

vector<int> depth;
vector<vector<int>> adj;
vector<pair<int, int>> euler;

void Dfs(int u, int p) {
  euler.emplace_back(p, u);
  for (auto v : adj[u]) if (v != p) {
    depth[v] = depth[u] + 1;
    Dfs(v, u);
  }
  euler.emplace_back(u, p);
}

void Init(int N, vector<int> A, vector<int> B) {
  ::N = N, ::A = A, ::B = B;
  adj.resize(N);
  depth.resize(N);
  for (int i = 0; i + 1 < N; i++) {
    adj[A[i]].emplace_back(B[i]);
    adj[B[i]].emplace_back(A[i]);
    name[{A[i], B[i]}] = name[{B[i], A[i]}] = i;
  }
  Dfs(0, -1);
}

}

void InitAnya(int N , int A[] , int B[]) {
  Init(N, vector<int>(A, A + N - 1), vector<int>(B, B + N - 1));
}

void Anya(int C[]) {
  vector<int> sum(1001);
  for (int i = 0; i <= 1000; i++) {
    if (i > 0) {
      sum[i] = sum[i - 1];
    }
    if (i < (int) euler.size()) {
      int u = euler[i].first, v = euler[i].second;
      int id = name[{u, v}];
      if (u == -1 || v == -1) {
        continue;
      }
      if (depth[u] < depth[v]) {
        sum[i] += C[id];
      } else {
        sum[i] -= C[id];
      }
    }
  }
  int ptr = 0;
  for (int i = 0; i + 1 < N; i++) {
    Save(ptr++, C[i]);
  }
  for(int i = 0; i <= 1000; i += 20) {
    for (int j = 0; j < 9; j++) {
      if (sum[i] & (1 << j)) {
        Save(ptr++, 1);
      } else {
        Save(ptr++, 0);
      }
    }
  }
}

Boris

#include "Borislib.h"
#include <bits/stdc++.h>
using namespace std;

namespace {

int N;
vector<int> A, B;
map<pair<int, int>, int> name;

vector<int> depth;
vector<vector<int>> adj;
vector<pair<int, int>> euler;

void Dfs(int u, int p) {
  euler.emplace_back(p, u);
  for (auto v : adj[u]) if (v != p) {
    depth[v] = depth[u] + 1;
    Dfs(v, u);
  }
  euler.emplace_back(u, p);
}

void Init(int N, vector<int> A, vector<int> B) {
  ::N = N, ::A = A, ::B = B;
  adj.resize(N);
  depth.resize(N);
  for (int i = 0; i + 1 < N; i++) {
    adj[A[i]].emplace_back(B[i]);
    adj[B[i]].emplace_back(A[i]);
    name[{A[i], B[i]}] = name[{B[i], A[i]}] = i;
  }
  Dfs(0, -1);
}

}

void InitBoris(int N , int A[] , int B[]) {
  Init(N, vector<int>(A, A + N - 1), vector<int>(B, B + N - 1));
}

int Boris(int city) {
  if (city == 0) {
    return 0;
  }
  int where = -1;
  for (int i = 0; i < (int) euler.size(); i++) {
    if (euler[i].second == city) {
      where = i;
      break;
    }
  }
  assert(where != -1);
  vector<int> savepos(1001, -1);
  int ptr = 0;
  for (int i = 0; i + 1 < N; i++) {
    ptr += 1;
  }
  for(int i = 0; i <= 1000; i += 20) {
    savepos[i] = ptr;
    for (int j = 0; j < 9; j++) {
      ptr += 1;
    }
  }
  int ans = 0, loc = -1;
  for (int cnt = 0;; cnt++) {
    if (savepos[where + cnt] != -1) {
      for (int j = where + 1; j <= where + cnt; j++) {
        if (j < (int) euler.size()) {
          int u = euler[j].first, v = euler[j].second;
          if (u == -1 || v == -1) {
            continue;
          }
          if (depth[u] < depth[v]) {
            ans -= Ask(name[{euler[j].first, euler[j].second}]);
          } else {
            ans += Ask(name[{euler[j].first, euler[j].second}]);
          }
        }
      }
      loc = where + cnt;
      break;
    }
    if (savepos[where - cnt] != -1) {
      for (int j = where; j > where - cnt; j--) {
        if (j < (int) euler.size()) {
          int u = euler[j].first, v = euler[j].second;
          if (u == -1 || v == -1) {
            continue;
          }
          if (depth[u] < depth[v]) {
            ans += Ask(name[{euler[j].first, euler[j].second}]);
          } else {
            ans -= Ask(name[{euler[j].first, euler[j].second}]);
          }
        }
      }
      loc = where - cnt;
      break;
    }
  }
  assert(loc != -1 && savepos[loc] != -1);
  for (int j = 0; j < 9; j++) {
    if (Ask(savepos[loc] + j)) {
      ans += 1 << j;
    }
  }
  return ans;
}

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