Submission #118483

#	Time	Username	Problem	Language	Result	Execution time	Memory
118483		IOrtroiii	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	44 ms	8452 KiB

Joi

#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 (need == 0) return;
			if (::where[v] != where) {
         reva[a[v]] = v;
         --need;
      }
      extra_dfs(v, where, need);
   }
}

void Joi(int n, int m, int from[], int to[], ll x, int task) {
   for (int i = 0; i < m; ++i) {
      g[from[i]].emplace_back(to[i]);
      g[to[i]].emplace_back(from[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);
   }
}

Ioi

#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 (need == 0) return;
			if (::where[v] != where) {
         reva[a[v]] = v;
         --need;
      }
      extra_dfs(v, where, need);
   }
}

ll ans = 0;

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

ll Ioi(int n, int m, int from[], int to[], int pos, int val, int task) {
   for (int i = 0; i < m; ++i) {
      g[from[i]].emplace_back(to[i]);
      g[to[i]].emplace_back(from[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[pos]]) {
      can[v] = true;
   }
   ans = (ll) val * (1ll << a[pos]);
   solve(pos);
   return ans;
}

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