제출 #1039489

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1039489		juicy	Amusement Park (JOI17_amusement_park)	C++17	100 / 100	31 ms	35148 KiB

Joi

#include "Joi.h"

#include <bits/stdc++.h>

using namespace std;

namespace {
  bitset<10000> G[10000];
  vector<int> g[10000];
  bool vis[10000];  
  int pos[10000], pr[10000], c[10000];
  int timer = 0;

  void dfs(int u) {
    vis[u] = 1;
    pos[timer++] = u;
    for (int v : g[u]) {
      if (!vis[v]) {
        G[u][v] = G[v][u] = 1;
        pr[v] = u;
        dfs(v);
      }
    }
  }
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
  for (int i = 0; i < M; ++i) {
    g[A[i]].push_back(B[i]);
    g[B[i]].push_back(A[i]);
  }
  dfs(0);
  vector<int> tr;
  for (int i = 0; i < 60; ++i) {
    tr.push_back(pos[i]);
    c[pos[i]] = i;
  }
  vector<vector<int>> tree(N);
  for (int u : tr) {
    tree[u] = tr;
  }
  for (int i = 60; i < N; ++i) {
    int u = pos[i], p = pr[u];
    auto &tr = tree[u];
    tr = tree[p];
    int d = -1;
    for (int x : tr) {
      if (x != p) {
        int deg = 0;
        for (int y : tr) {
          if (G[x][y]) {
            ++deg;
          }
        }
        if (deg == 1) {
          d = x;
          break;
        }
      }
    }
    c[u] = c[d];
    tr.erase(find(tr.begin(), tr.end(), d));
    tr.push_back(u);
  }
  for (int i = 0; i < N; ++i) {
    MessageBoard(i, X >> c[i] & 1);
  }
}

Ioi

#include "Ioi.h"

#include <bits/stdc++.h>

using namespace std;

namespace {
  void __print() {
    cerr << "]\n";
  }

  template<class T, class... V> 
  void __print(T t, V... v) {
    cerr << t;
    if (sizeof...(v)) {
      cerr << ", ";
    }
    __print(v...);
  }

  #define debug(x...) cerr << "[" << #x << "] = ["; __print(x); 

  bitset<10000> G[10000];
  vector<int> g[10000], gph[10000];
  bool vis[10000];  
  int pos[10000], pr[10000], c[10000], val[10000];
  int timer = 0;

  void dfs(int u) {
    vis[u] = 1;
    pos[timer++] = u;
    for (int v : g[u]) {
      if (!vis[v]) {
        G[u][v] = G[v][u] = 1;
        pr[v] = u;
        dfs(v);
      }
    }
  }

  void DFS(int u) {
    vis[u] = 1;
    for (int v : gph[u]) {
      if (!vis[v]) {
        val[v] = Move(v);
        DFS(v);
        Move(u);
      }
    }
  }
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
  for (int i = 0; i < M; ++i) {
    g[A[i]].push_back(B[i]);
    g[B[i]].push_back(A[i]);
  }
  dfs(0);
  vector<int> tr;
  for (int i = 0; i < 60; ++i) {
    tr.push_back(pos[i]);
    c[pos[i]] = i;
  }
  vector<vector<int>> tree(N);
  for (int u : tr) {
    tree[u] = tr;
  }
  for (int i = 60; i < N; ++i) {
    int u = pos[i], p = pr[u];
    auto &tr = tree[u];
    tr = tree[p];
    int d = -1;
    for (int x : tr) {
      if (x != p) {
        int deg = 0;
        for (int y : tr) {
          if (G[x][y]) {
            ++deg;
          }
        }
        if (deg == 1) {
          d = x;
          break;
        }
      }
    }
    c[u] = c[d];
    tr.erase(find(tr.begin(), tr.end(), d));
    tr.push_back(u);
  }
  val[P] = V;
  for (int x : tree[P]) {
    for (int y : tree[P]) {
      if (G[x][y]) {
        gph[x].push_back(y);
        gph[y].push_back(x);
      }
    }
  }
  fill(vis, vis + N, 0);
  DFS(P);
  long long res = 0;
  for (int x : tree[P]) {
    if (val[x]) {
      res += 1LL << c[x];
    }
  }
  return res;
}

컴파일 시 표준 에러 (stderr) 메시지

Ioi.cpp:8:8: warning: 'void {anonymous}::__print()' defined but not used [-Wunused-function]
    8 |   void __print() {
      |        ^~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 55 / 55
• Subtask 5: 17 / 17