Submission #39349

#	Time	Username	Problem	Language	Result	Execution time	Memory
39349		funcsr	Snowy Roads (JOI16_snowy)	C++14	100 / 100	22 ms	4248 KiB

Anya

#include "Anyalib.h"
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <cassert>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define index(x, y) (int)(lower_bound(all(x), y) - x.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
const int D = 11;

namespace A {
  int N;
  vector<P> G[500];
  int dp[500][20];

  int dfs(int x, int p, int d) {
    if (dp[x][d] != -1) return dp[x][d];
    int s = (d==0);
    for (P pp : G[x]) if (pp._1 != p) {
      int t = pp._1;
      s += min(dfs(t, x, 0), d<D?dfs(t, x, d+1):INF);
    }
    return dp[x][d] = s;
  }
  vector<int> pts;
  void dfs2(int x, int p, int d) {
    if (d == 0) pts.pb(x);
    for (P pp : G[x]) if (pp._1 != p) {
      int t = pp._1;
      if (dfs(t, x, 0) <= (d<D?dfs(t, x, d+1):INF)) {
        dfs2(t, x, 0);
      }
      else {
        dfs2(t, x, d+1);
      }
    }
  }
  void InitAnya(int NN, int A[] , int B[]) {
    N = NN;
    rep(i, N-1) {
      G[A[i]].pb(P(B[i], i));
      G[B[i]].pb(P(A[i], i));
    }
    rep(i, N) rep(j, D+1) dp[i][j] = -1;
    int num = dfs(0, -1, 0);
    //cout<<"num="<<num<<"\n";
    assert(num <= 55);
    dfs2(0, -1, 0);
    //cout<<"{"; for (int x:  pts)cout<<x<<",";cout<<"}\n";
  }
  int C[500], R[500];
  void dfs3(int x, int p, int r) {
    R[x] = r;
    for (P pp : G[x]) if (pp._1 != p) {
      int t = pp._1;
      dfs3(t, x, r+C[pp._2]);
    }
  }
  void Anya(int CC[]) {
    //rep(i, N-1) cout<<CC[i];cout<<"\n";
    rep(i, N-1) C[i] = CC[i], Save(i, C[i]);
    dfs3(0, -1, 0);
    rep(i, pts.size()) {
      int v = pts[i];
      //cout<<"ans["<<v<<"]="<<R[v]<<"\n";
      rep(o, 9) {
        Save(N-1+9*i+o, (R[v]>>o)&1);
      }
    }
  }
}
void InitAnya(int NN, int A[] , int B[]) {
  A::InitAnya(NN, A, B);
}

void Anya(int CC[]) {
  A::Anya(CC);
}

Boris

#include "Borislib.h"
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <cassert>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> P2;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define index(x, y) (int)(lower_bound(all(x), y) - x.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
const int D = 11;

int N;
vector<P> G[500];
int dp[500][20];
int U[500], Ue[500];

int dfs(int x, int p, int d) {
  if (dp[x][d] != -1) return dp[x][d];
  U[x] = p;
  int s = (d==0);
  for (P pp : G[x]) if (pp._1 != p) {
    int t = pp._1;
    Ue[t] = pp._2;
    s += min(dfs(t, x, 0), d<D?dfs(t, x, d+1):INF);
  }
  return dp[x][d] = s;
}
vector<int> pts;
void dfs2(int x, int p, int d) {
  if (d == 0) pts.pb(x);
  for (P pp : G[x]) if (pp._1 != p) {
    int t = pp._1;
    if (dfs(t, x, 0) <= (d<D?dfs(t, x, d+1):INF)) {
      dfs2(t, x, 0);
    }
    else {
      dfs2(t, x, d+1);
    }
  }
}

int pos[500];
void InitBoris(int NN, int A[], int B[]) {
  N = NN;
  rep(i, N-1) {
    G[A[i]].pb(P(B[i], i));
    G[B[i]].pb(P(A[i], i));
  }
  rep(i, N) rep(j, D+1) dp[i][j] = -1;
  int num = dfs(0, -1, 0);
  assert(num <= 55);
  dfs2(0, -1, 0);
  rep(i, N) pos[i] = -1;
  rep(i, pts.size()) pos[pts[i]] = i;
  //cout<<"{"; for (int x:  pts)cout<<x<<",";cout<<"}\n";
}

int Boris(int x) {
  int s = 0, up = 0;
  while (pos[x] == -1) s += Ask(Ue[x]), x = U[x], up++;
  assert(up <= D);
  //while (pos[x] == -1) cout<<"up->"<<U[x]<<"\n",s += Ask(Ue[x]), x = U[x];
  int base = N-1+9*pos[x];
  int ans = 0;
  rep(o, 9) ans |= (Ask(base+o)<<o);
  //cout<<"boris("<<x<<") = "<<ans<<"\n";
  return ans+s;
}

Compilation message (stderr)

Anya.cpp: In function 'void A::Anya(int*)':
Anya.cpp:11:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
Anya.cpp:73:5: note: in expansion of macro 'rep'
     rep(i, pts.size()) {
     ^

Boris.cpp: In function 'void InitBoris(int, int*, int*)':
Boris.cpp:12:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
Boris.cpp:64:3: note: in expansion of macro 'rep'
   rep(i, pts.size()) pos[pts[i]] = i;
   ^

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