oj.uz

Submission #39347

# Submission time Handle Problem Language Result Execution time Memory
39347 2018-01-12T04:13:23 Z funcsr None (JOI16_snowy) C++14
0 / 100
 16 ms 4248 KB 
#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;
//const int D = 1;

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) C[i] = CC[i], Save(i, C[i]);
    dfs3(0, -1, 0);
    rep(i, pts.size()) {
      int v = pts[i];
      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);
}

#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;
  while (pos[x] == -1) s += Ask(Ue[x]), x = U[x];
  //cout<<"boris("<<x<<")\n";
  //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)<<1);
  return ans+s;
}

Compilation message

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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4248 KB Output is correct
2 Correct 0 ms 4248 KB Output is correct
3 Correct 0 ms 4248 KB Output is correct
4 Correct 3 ms 4248 KB Output is correct
5 Correct 3 ms 4248 KB Output is correct
6 Correct 6 ms 4248 KB Output is correct
7 Correct 6 ms 4248 KB Output is correct
8 Correct 6 ms 4248 KB Output is correct
9 Incorrect 6 ms 4248 KB Wrong Answer [7]
10 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4248 KB Output is correct
2 Incorrect 12 ms 4248 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 4248 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 4248 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -