oj.uz

답안 #118440

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
118440 2019-06-19T03:36:42 Z IOrtroiii Amusement Park (JOI17_amusement_park) C++14
0 / 100
 15 ms 3456 KB 
#include "Joi.h"

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 10100;

static int tot;
static vector<int> g[N];
static vector<int> comp[N];
static int where[N];
static int a[N];
static bool visit[N];
static int reva[60];

static void dfs(int u) {
   where[u] = tot;
   comp[tot].emplace_back(u);
   for (int v : g[u]) {
      if (comp[tot].size() == 60) {
         return;
      } else if (!where[v]) {
         dfs(v);
      }
   }
}

static void extra_dfs(int u, int where, int &need) {
   visit[u] = true;
   for (int v : g[u]) if (!visit[v]) {
      if (::where[v] != where) {
         reva[a[v]] = v;
         --need;
      }
      if (need == 0) return;
      extra_dfs(v, where, need);
   }
}

void Joi(int n, int m, int a[], int b[], ll x, int t) {
   for (int i = 0; i < m; ++i) {
      g[a[i]].emplace_back(b[i]);
      g[b[i]].emplace_back(a[i]);
   }
   for (int i = 0; i < n; ++i) if (!where[i]) {
      ++tot; dfs(i);
   }
   for (int i = 1; i <= tot; ++i) {
      if (comp[i].size() == 60) {
         int ptr = 0;
         for (int u : comp[i]) {
            a[u] = ptr++;
         }
         for (int u : comp[i]) {
            vector<int> ng;
            for (int v : g[u]) {
               if (where[v] == where[u]) {
                  ng.emplace_back(v);
               }
            }
            g[u].swap(ng);
         }
      }
   }
   for (int i = 1; i <= tot; ++i) if (comp[i].size() < 60) {
      memset(reva, -1, sizeof reva);
      int need = 60 - comp[i].size();
      extra_dfs(comp[i].back(), i, need);
      int ptr = 0;
      vector<int> ncomp;
      for (int j = 0; j < 60; ++j) {
         if (~reva[j]) {
            ncomp.emplace_back(reva[j]);
         } else {
            a[comp[i][ptr]] = j;
            ncomp.push_back(comp[i][ptr++]);
         }
      }
      comp[i].swap(ncomp);
      for (int u : comp[i]) {
         visit[u] = false;
      }
   }
   for (int i = 0; i < n; ++i) {
      MessageBoard(i, (x >> a[i]) & 1);
   }
}

#include "Ioi.h"

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 10100;

static int tot;
static vector<int> g[N];
static vector<int> comp[N];
static int where[N];
static int a[N];
static bool visit[N];
static int reva[60];
static int can[N];

static void dfs(int u) {
   where[u] = tot;
   comp[tot].emplace_back(u);
   for (int v : g[u]) {
      if (comp[tot].size() == 60) {
         return;
      } else if (!where[v]) {
         dfs(v);
      }
   }
}

static void extra_dfs(int u, int where, int &need) {
   visit[u] = true;
   for (int v : g[u]) if (!visit[v]) {
      if (::where[v] != where) {
         reva[a[v]] = v;
         --need;
      }
      if (need == 0) return;
      extra_dfs(v, where, need);
   }
}

ll ans = 0;

void dfs_solve(int u) {
   visit[u] = true;
   for (int v : g[u]) {
      if (can[v] && !visit[v]) {
         bool t = Move(v);
         ans |= (1ll << a[v]) * t;
         dfs_solve(v);
         Move(u);
      }
   }
}

ll 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]].emplace_back(b[i]);
      g[b[i]].emplace_back(a[i]);
   }
   for (int i = 0; i < n; ++i) if (!where[i]) {
      ++tot; dfs(i);
   }
   for (int i = 1; i <= tot; ++i) {
      if (comp[i].size() == 60) {
         int ptr = 0;
         for (int u : comp[i]) {
            a[u] = ptr++;
         }
         for (int u : comp[i]) {
            vector<int> ng;
            for (int v : g[u]) {
               if (where[v] == where[u]) {
                  ng.emplace_back(v);
               }
            }
            g[u].swap(ng);
         }
      }
   }
   for (int i = 1; i <= tot; ++i) if (comp[i].size() < 60) {
      memset(reva, -1, sizeof reva);
      int need = 60 - comp[i].size();
      extra_dfs(comp[i].back(), i, need);
      int ptr = 0;
      vector<int> ncomp;
      for (int j = 0; j < 60; ++j) {
         if (~reva[j]) {
            ncomp.emplace_back(reva[j]);
         } else {
            a[comp[i][ptr]] = j;
            ncomp.push_back(comp[i][ptr++]);
         }
      }
      comp[i].swap(ncomp);
      for (int u : comp[i]) {
         visit[u] = false;
      }
   }
   for (int v : comp[where[p]]) {
      can[v] = true;
   }
   ans = v * (1ll << a[p]);
   dfs_solve(p);
   return ans;
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 1536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 15 ms 3456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 2304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 15 ms 3456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 14 ms 3448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -