Submission #1170694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170694		yellowtoad	Amusement Park (JOI17_amusement_park)	C++20	10 / 100	28 ms	8264 KiB

Joi

#include "Joi.h"
#include <iostream>
#include <vector>
using namespace std;

int vis_Joi[10010], ord_Joi[10010], cnt_Joi;
vector<int> edge_Joi[10010];

void dfs_Joi(int u) {
  vis_Joi[u] = 1;
  ord_Joi[u] = cnt_Joi++;
  for (int i = 0; i < edge_Joi[u].size(); i++) if (!vis_Joi[edge_Joi[u][i]]) dfs_Joi(edge_Joi[u][i]);
}

void Joi(int n, int m, int A[], int B[], long long X, int T) {
  for (int i = 0; i < m; i++) {
    edge_Joi[A[i]].push_back(B[i]);
    edge_Joi[B[i]].push_back(A[i]);
  }
  dfs_Joi(0);
  for (int i = 0; i < n; i++) MessageBoard(i,((X>>(ord_Joi[i]%60)))%2);
}

Ioi

#include "Ioi.h"
#include <iostream>
#include <vector>
using namespace std;

long long vis[10010], ord[10010], cnt, p[10010], ans[70], hv[10010][70], ok[70], ord2[10010], uu;
vector<long long> edge[10010], adj[10010], path, tmp, viss;
bool can, done;

void dfs(int u) {
  vis[u] = 1;
  ord[u] = cnt++;
  hv[u][ord[u]%60] = 1;
  for (int i = 0; i < edge[u].size(); i++) {
    if (!vis[edge[u][i]]) {
      adj[u].push_back(edge[u][i]);
      p[edge[u][i]] = u;
      dfs(edge[u][i]);
      for (int j = 0; j < 60; j++) hv[u][j] |= hv[edge[u][i]][j];
    }
  }
  ord2[u] = cnt;
}

bool check(int u) {
  for (int i = 0; i < 60; i++) if (!hv[u][i]) return 0;
  return 1; 
}

void dfs1(int u) {
  for (int i = 0; i < 60; i++) if (!ok[i] && hv[u][i]) goto skip;
  return;
  skip:;
  ok[ord[u]%60] = vis[u] = 1;
  for (int i = 0; i < adj[u].size(); i++) dfs1(adj[u][i]);
}

void dfs2(int u, int lst, int need_check) {
  if (!can) return;
  if (need_check && (u != uu) && (ord[u] <= ord[lst]) && (ord2[lst] <= ord2[u])) {
    can = 0;
    return;
  }
  tmp.push_back(u);
  vis[u] = 0;
  for (int i = 0; i < adj[u].size(); i++) {
    if ((vis[adj[u][i]]) && (!((ord[adj[u][i]] <= ord[lst]) && (ord2[lst] <= ord2[adj[u][i]])))) {
      dfs2(adj[u][i],lst,0);
      tmp.push_back(u);
    }
  }
  for (int i = 0; i < adj[u].size(); i++) {
    if ((vis[adj[u][i]]) && ((ord[adj[u][i]] <= ord[lst]) && (ord2[lst] <= ord2[adj[u][i]]))) {
      dfs2(adj[u][i],lst,0);
      tmp.push_back(u);
    }
  }
  if ((p[u] != -1) && (vis[p[u]])) dfs2(p[u],lst,1);
}

long long Ioi(int n, int m, int A[], int B[], int P, int V, int T) {
  for (int i = 0; i < m; i++) {
    edge[A[i]].push_back(B[i]);
    edge[B[i]].push_back(A[i]);
  }
  for (int i = 0; i < n; i++) p[i] = -1;
  dfs(0);
  int u = P;
  for (int i = 0; i < n; i++) vis[i] = 0;
  ok[ord[u]%60] = vis[u] = 1;
  while (!check(u)) u = p[u], ok[ord[u]%60] = vis[u] = 1;
  uu = u;
  dfs1(u);
  for (int i = 0; i < n; i++) if (vis[i]) viss.push_back(i);
  for (int i = 0; i < n; i++) {
    if (vis[i]) {
      cnt = 0;
      for (int j = 0; j < adj[i].size(); j++) cnt += vis[adj[i][j]];
      if (p[i] != -1) cnt += vis[p[i]];
      if (cnt != 1) continue;
      tmp.clear();
      can = 1; done = 0;
      dfs2(P,i,1);
      for (int j = 0; j < viss.size(); j++) vis[viss[j]] = 1;
      while (tmp.back() != i) tmp.pop_back();
      if (can && (path.empty() || (tmp.size() < path.size()))) path = tmp;
    }
  }
  u = P;
  ans[ord[u]%60] = V;
  for (int i = 0; i < path.size(); i++) {
    if (u == path[i]) continue;
    u = path[i];
    ans[ord[u]%60] = Move(u);
  }
  long long x = 0;
  for (int i = 0; i < 60; i++) x += (ans[i]<<i);
  return x;
}

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