oj.uz

답안 #283020

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
283020 2020-08-25T08:41:30 Z rama_pang Snowy Roads (JOI16_snowy) C++14
0 / 100
 52 ms 1520 KB 
#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);
      }
    }
  }
}

#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;
    }
  }
  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 (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 (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(savepos[loc] != -1);
  for (int j = 0; j < 9; j++) {
    if (Ask(savepos[loc] + j)) {
      ans += 1 << j;
    }
  }
  return ans;
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 944 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 1188 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 33 ms 1476 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 52 ms 1520 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -