oj.uz

Submission #500028

# Submission time Handle Problem Language Result Execution time Memory
500028 2021-12-30T09:42:11 Z 600Mihnea Amusement Park (JOI17_amusement_park) C++17
0 / 100
 27 ms 6592 KB 
#include "Joi.h"
#include <bits/stdc++.h>

using namespace std;

const int BITS = 10;


void Joi(int N, int M, int A[], int B[], long long X, int T) {
  vector<vector<int>> g(N);
  vector<int> color(N, -1);

  for (int i = 0; i < M; i++) {
    g[A[i]].push_back(B[i]);
    g[B[i]].push_back(A[i]);
  }


  vector<bool> vis(N, 0);
  vector<vector<int>> ng(N);

  function<void(int)> makeG = [&] (int a) {
    vis[a] = 1;
    for (auto &b : g[a]) {
      if (!vis[b]) {
        ng[a].push_back(b);
        makeG(b);
      }
    }
  };
  makeG(0);
  g = ng;

  function<void(int)> draw = [&] (int a) {
    vector<int> all;
    queue<int> q;
    q.push(a);
    all.push_back(a);
    while (!q.empty()) {
      int x = q.front();
      q.pop();
      for (auto &y : g[x]) {
        if ((int) all.size() + 1 > BITS) break;
        q.push(y);
        all.push_back(y);
      }
    }
    assert((int) all.size() <= BITS);
    for (int i = 0; i < (int) all.size(); i++) {
      color[all[i]] = i;
    }
    for (int i = 0; i < (int) all.size(); i++) {
      for (auto &v : g[all[i]]) {
        if (color[v] == -1) {
          draw(v);
        }
      }
    }
  };
  draw(0);
  for (auto &x : color) assert(0 <= x && x < BITS);


  vector<int> numBits(BITS);
  for (int i = 0; i < BITS; i++) {
    if (X & (1LL << i)) {
      numBits[i] = 1;
    } else {
      numBits[i] = 0;
    }
  }



  for(int i = 0; i < N; i++) {
    MessageBoard(i, numBits[color[i]]);
  }
}



#include "Ioi.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int BITS = 10;

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
  vector<vector<int>> g(N);
  vector<int> color(N, -1);
  vector<int> parrent(N, -1);

  for (int i = 0; i < M; i++) {
    g[A[i]].push_back(B[i]);
    g[B[i]].push_back(A[i]);
  }

  vector<bool> vis(N, 0);
  vector<int> sub(N);
  vector<vector<int>> ng(N);

  function<void(int)> makeG = [&] (int a) {
    vis[a] = 1;
    sub[a] = 1;
    for (auto &b : g[a]) {
      if (!vis[b]) {
        ng[a].push_back(b);
        makeG(b);
        parrent[b] = a;
        sub[a] += sub[b];
      }
    }
  };
  makeG(0);
  g = ng;

  map<int, vector<pair<int, int>>> guys;

  function<void(int)> draw = [&] (int a) {
    vector<pair<int, int>> all;
    queue<int> q;
    q.push(a);
    vector<int> vrts = {a};
    while (!q.empty()) {
      int x = q.front();
      q.pop();
      for (auto &y : g[x]) {
        if ((int) vrts.size() + 1 > BITS) break;
        q.push(y);
        vrts.push_back(y);
        all.push_back({x, y});
      }
    }
    guys[a] = all;
    assert((int) all.size() <= BITS);
    for (int i = 0; i < (int) vrts.size(); i++) {
      color[vrts[i]] = i;
    }
    for (int i = 0; i < (int) vrts.size(); i++) {
      for (auto &v : g[vrts[i]]) {
        if (color[v] == -1) {
          draw(v);
        }
      }
    }
  };
  draw(0);
  while (sub[P] < BITS || !guys.count(P)) {
    V = Move(parrent[P]);
    P = parrent[P];
  }
  vector<pair<int, int>> all = guys[P];

  for (int i = 0; i < N; i++) g[i].clear();

  for (auto &it : all) g[it.first].push_back(it.second);

  int done = 0;
  ll solu = 0;

  function<void(int)> expl = [&] (int a) {
    solu += (1LL << color[a]) * V;
    done++;
    for (auto &b : g[a]) {
      if (done == BITS) break;
      V = Move(b);
      if (done == BITS) break;
      expl(b);
      if (done == BITS) break;
      V = Move(a);
      if (done == BITS) break;
    }
  };

  expl(P);

  assert(done == BITS);
  for (auto &x : color) assert(0 <= x && x < BITS);



  vector<int> numBits(BITS, -1);
  int needBits = BITS;


  return solu;
}

Compilation message

Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:106:7: warning: unused variable 'needBits' [-Wunused-variable]
  106 |   int needBits = BITS;
      |       ^~~~~~~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 55.0

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

Subtask #5
0 / 17.0

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