QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#295904#6335. Belt Conveyorchy12321Compile Error//C++204.8kb2024-01-01 14:46:512024-01-01 14:46:51

Judging History

你现在查看的是最新测评结果

  • [2024-01-01 14:46:51]
  • 评测
  • [2024-01-01 14:46:51]
  • 提交

answer

#include "conveyor.h"

#include <cstdio>
#include <cstdlib>
#include <random>
#include <utility>
#include <vector>

namespace {

const int INVALID_X_LENGTH = 1;
const int INVALID_X_RANGE = 2;
const int INVALID_Y_LENGTH = 3;
const int INVALID_Y_RANGE = 4;
const int QUERY_LIMIT_EXCEEDED = 5;
const int INVALID_A_LENGTH = 6;
const int INVALID_A_RANGE = 7;
const int WRONG_A = 8;
const int ANSWER_TWICE = 9;
const int NO_ANSWER = 10;

const int QUERY_LIMIT = 30;

int N;
std::vector<int> A, B, C;

int query_count = 0;
bool answered = false;

void WrongAnswer(int code) {
  printf("Wrong Answer [%d]\n", code);
  exit(0);
}

std::mt19937 rng(0);

int random_select(const std::vector<int> &v) {
  return v[std::uniform_int_distribution<int>(0, v.size() - 1)(rng)];
}

} // namespace

std::vector<int> Query(std::vector<int> x, std::vector<int> y) {
  if (int(x.size()) != N - 1) {
    WrongAnswer(INVALID_X_LENGTH);
  }
  for (int i = 0; i < N - 1; i++) {
    if (x[i] != 0 && x[i] != 1) {
      WrongAnswer(INVALID_X_RANGE);
    }
  }
  if (int(y.size()) != N) {
    WrongAnswer(INVALID_Y_LENGTH);
  }
  for (int i = 0; i < N; i++) {
    if (y[i] != 0 && y[i] != 1) {
      WrongAnswer(INVALID_Y_RANGE);
    }
  }
  query_count++;
  if (query_count > QUERY_LIMIT) {
    WrongAnswer(QUERY_LIMIT_EXCEEDED);
  }
  std::vector<int> z(N, 0);
  std::vector<std::vector<int>> t(N);
  for (int i = 0; i < N - 1; i++) {
    int a = A[i], b = B[i];
    if (x[i] ^ C[i]) {
      std::swap(a, b);
    }
    t[a].push_back(b);
  }
  for (int i = 0; i < N; i++) {
    if (y[i]) {
      if (t[i].empty()) {
        z[i] = 1;
      } else {
        z[random_select(t[i])] = 1;
      }
    }
  }
  return z;
}

void Answer(std::vector<int> a) {
  if (answered) {
    WrongAnswer(ANSWER_TWICE);
  }
  answered = true;
  if (int(a.size()) != N - 1) {
    WrongAnswer(INVALID_A_LENGTH);
  }
  for (int i = 0; i < N - 1; i++) {
    if (a[i] != 0 && a[i] != 1) {
      WrongAnswer(INVALID_A_RANGE);
    }
  }
  if (a != C) {
    WrongAnswer(WRONG_A);
  }
}

#include <bits/stdc++.h>

using namespace std;

constexpr int MAXN = 1e5 + 10;

int dep[MAXN], deg[MAXN];

vector<int> G[MAXN], d[3];

void Solve(int n, vector<int> a, vector<int> b) {
    function<void(int, int)> dfs = [&](int u, int fa) {
        for (int i : G[u]) {
            int v = u ^ a[i] ^ b[i];
            if (v != fa) dep[v] = dep[u] + 1, dfs(v, u);
        }
    };
    
    vector<int> dir(n - 1, -1);
    for (int i = 0; i < n - 1; i++) {
        G[a[i]].emplace_back(i), G[b[i]].emplace_back(i);
        deg[a[i]]++, deg[b[i]]++;
    }
    dfs(0, -1);
    for (int i = 0; i < n; i++) d[dep[i] % 3].emplace_back(i);
    while (!(d[0].empty() && d[1].empty() && d[2].empty())) {
        vector<int> V(n), E(n - 1);
        for (int u : d[0]) {
            V[u] = 1;
            for (int i : G[u]) {
                if ((u == a[i] && dir[i] == 0) || (u == b[i] && dir[i] == 1)) E[i] = 1;
            }
        }
        vector<int> now = Query(E, V);
        for (int u : d[0]) {
            if (now[u]) {
                for (int i : G[u]) {
                    if (dir[i] == -1) {
                        dir[i] = u == b[i] ? 0 : 1;
                        deg[a[i]]--, deg[b[i]]--;
                    }
                }
            } else {
              for (int i : G[u]) {
                  if (now[u ^ a[i] ^ b[i]]) {
                      dir[i] = u == a[i] ? 0 : 1;
                      deg[a[i]]--, deg[b[i]]--;
                  }
              }
            }
        }
        for (int i : {0, 1, 2}) {
            for (int j = d[i].size() - 1; j >= 0; j--) {
                if (!deg[d[i][j]]) d[i].erase(d[i].begin() + j);
            }
        }
        sort(d, d + 3, [&](vector<int> x, vector<int> y) {return x.size() > y.size();});
    }
    Answer(dir);
}

int main(int argc, char **argv) {
  if (argc >= 2) {
    long long seed = atoll(argv[1]);
    rng.seed(seed);
  }

  if (scanf("%d", &N) != 1) {
    fprintf(stderr, "Error while reading input.\n");
    exit(1);
  }
  A.resize(N - 1);
  B.resize(N - 1);
  C.resize(N - 1);
  for (int i = 0; i < N - 1; i++) {
    if (scanf("%d", &A[i]) != 1) {
      fprintf(stderr, "Error while reading input.\n");
      exit(1);
    }
  }
  for (int i = 0; i < N - 1; i++) {
    if (scanf("%d", &B[i]) != 1) {
      fprintf(stderr, "Error while reading input.\n");
      exit(1);
    }
  }
  for (int i = 0; i < N - 1; i++) {
    if (scanf("%d", &C[i]) != 1) {
      fprintf(stderr, "Error while reading input.\n");
      exit(1);
    }
  }
  Solve(N, A, B);
  if (!answered) {
    WrongAnswer(NO_ANSWER);
  }
  printf("Accepted: %d\n", query_count);
  return 0;
}

详细

/usr/bin/ld: /tmp/ccWwWluu.o: in function `Answer(std::vector<int, std::allocator<int> >)':
answer.code:(.text+0x380): multiple definition of `Answer(std::vector<int, std::allocator<int> >)'; /tmp/ccrUSvXt.o:implementer.cpp:(.text+0x400): first defined here
/usr/bin/ld: /tmp/ccWwWluu.o: in function `Query(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)':
answer.code:(.text+0x1850): multiple definition of `Query(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'; /tmp/ccrUSvXt.o:implementer.cpp:(.text+0x5a0): first defined here
/usr/bin/ld: /tmp/ccWwWluu.o: in function `main':
answer.code:(.text.startup+0x0): multiple definition of `main'; /tmp/ccrUSvXt.o:implementer.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status