Submission #969154

#	Time	Username	Problem	Language	Result	Execution time	Memory
969154		abczz	Snowy Roads (JOI16_snowy)	C++14	100 / 100	17 ms	1996 KiB

Anya

#include "Anyalib.h"
#include <iostream>
#include <array>
#include <vector>
#define ll long long
 
using namespace std;
 
vector <array<ll, 2> > adj[500];
vector <int> c;
ll n, sz, f, z, q, D[500], cnt[12];
 
void dfs(ll u, ll p, ll w) {
  D[u] = w;
  ++cnt[w];
  for (auto [v, x] : adj[u]) {
    if (v != p) dfs(v, u, (w+1)%12);
  }
}
 
void dfs2(ll u, ll p, ll w) {
  for (auto [v, x] : adj[u]) {
    if (v != p) {
      dfs2(v, u, w+c[x]);
      if (D[v] != z) Save(sz++, c[x]);
    }
  }
  if (u && D[u] == z) {
    for (int i=8; i>=0; --i) {
      if ((w & (1<<i))) Save(sz++, 1);
      else Save(sz++, 0);
    }
  }
}
 
void InitAnya(int N, int A[], int B[]) {
  n = N;
  for (int i=0; i<N; ++i) {
    adj[i].clear();
  }
  for (int i=0; i<N-1; ++i) {
    adj[A[i]].push_back({B[i],i});
    adj[B[i]].push_back({A[i],i});
  }
  dfs(0, -1, 0);
  f = 1e18;
  for (int i=0; i<12; ++i) {
    if (f > cnt[i] && cnt[i]) {
      f = cnt[i];
      z = i;
    }
  }
}
 
void Anya(int C[]) {
  c.clear();
  for (int i=0; i<n; ++i) c.push_back(C[i]);
  sz = 0;
  dfs2(0, -1, 0);
}

Boris

#include "Borislib.h"
#include <iostream>
#include <array>
#include <vector>
#define ll long long
 
using namespace std;
 
vector <array<ll, 2> > adj[500];
vector <int> c;
ll n, sz, f, z, q, D[500], cnt[12];
 
void dfs(ll u, ll p, ll w) {
  D[u] = w;
  ++cnt[w];
  for (auto [v, x] : adj[u]) {
    if (v != p) dfs(v, u, (w+1)%12);
  }
}
 
bool query(ll u, ll p) {
  bool B = 0, res;
  if (u == q) B = 1;
  for (auto [v, x] : adj[u]) {
    if (v != p) {
      res = query(v, u);
      if (res) f += Ask(sz);
      if (D[v] != z) sz++;
      B |= res;
    }
  }
  if (u && D[u] == z) {
    for (int i=8; i>=0; --i) {
      if (B) f += Ask(sz)*(1<<i);
      sz++;
    }
    return 0;
  }
  return B;
}
 
void InitBoris(int N, int A[], int B[]) {
  n = N;
  for (int i=0; i<N; ++i) {
    adj[i].clear();
  }
  for (int i=0; i<N-1; ++i) {
    adj[A[i]].push_back({B[i],i});
    adj[B[i]].push_back({A[i],i});
  }
  dfs(0, -1, 0);
  f = 1e18;
  for (int i=0; i<12; ++i) {
    if (f > cnt[i] && cnt[i]) {
      f = cnt[i];
      z = i;
    }
  }
}
 
int Boris(int city) {
  q = city;
  f = sz = 0;
  query(0, -1);
  return f;
}

Compilation message (stderr)

Anya.cpp: In function 'void dfs(long long int, long long int, long long int)':
Anya.cpp:16:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   16 |   for (auto [v, x] : adj[u]) {
      |             ^
Anya.cpp: In function 'void dfs2(long long int, long long int, long long int)':
Anya.cpp:22:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |   for (auto [v, x] : adj[u]) {
      |             ^

Boris.cpp: In function 'void dfs(long long int, long long int, long long int)':
Boris.cpp:16:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   16 |   for (auto [v, x] : adj[u]) {
      |             ^
Boris.cpp: In function 'bool query(long long int, long long int)':
Boris.cpp:24:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |   for (auto [v, x] : adj[u]) {
      |             ^

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