Submission #1169971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169971		fryingduc	Amusement Park (JOI17_amusement_park)	C++20	0 / 100	4065 ms	2028 KiB

Joi

#include "Joi.h"
#include "bits/stdc++.h"

using namespace std;

namespace {
  const int maxn = 1e4 + 4;
  vector<int> g[maxn];
  vector<int> adj[maxn];
  int n;
  int par[maxn];
  int h[maxn];
  int tin[maxn], timer, et[maxn];
  
  pair<int, int> bfs(int src) {
    queue<int> q;
    vector<int> d(n + 1, -1);
    d[src] = 0;
    par[src] = 0;
    q.push(src);
    memset(par, -1, sizeof(par));
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (auto v : g[u]) {
        if (d[v] == -1) {
          d[v] = d[u] + 1;
          par[v] = u;
          q.push(v);
        }
      }
    }
    int mx = *max_element(d.begin(), d.end());
    return make_pair(mx, src);
  }
  
  void dfs(int u) {
    tin[u] = ++timer;
    et[timer] = u;
    for (auto v : adj[u]) {
      h[v] = h[u] + 1;
      dfs(v);
    }
  }
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
  pair<int, int> opt = make_pair(-1, -1);
  pair<int, int> mn = make_pair(1e9, 1e9);
  n = N;
  for (int i = 0; i < n; ++i) {
    g[i].clear();
    adj[i].clear();
  }
  for (int i = 0; i < M; ++i) {
    g[A[i]].push_back(B[i]);
    g[B[i]].push_back(A[i]);
  }
  for (int i = 0; i < n; ++i) {
    pair<int, int> cur = bfs(i);
    opt = max(opt, cur);
    mn = min(mn, cur);
  }
  if (opt.first + 1 >= 60) {
    bfs(opt.second);
    for (int i = 0; i < n; ++i) {
      if (par[i] != -1) {
        adj[par[i]].push_back(i);
      }
    }
    dfs(opt.second);
    for (int i = 0; i < n; ++i) {
      MessageBoard(i, X >> (h[i] % 60) & 1);
    }
  } else {
//    cerr << mn.first << " " << mn.second << endl;
    bfs(mn.second);
    for (int i = 0; i < n; ++i) {
//      cerr << i << " " << par[i] << endl;
      if (par[i] != -1) {
        adj[par[i]].push_back(i);
      }
    }
    timer = 0;
    dfs(mn.second);
    for (int i = 0; i < n; ++i) {
//      cerr << et[i + 1] << " ";
      MessageBoard(et[i + 1], X >> (i % 60) & 1);
    }
  }
}

Ioi

#include "Ioi.h"
#include "bits/stdc++.h"

using namespace std;

namespace {
  const int maxn = 1e4 + 4;
  vector<int> g[maxn];
  vector<int> adj[maxn];
  int n;
  int par[maxn];
  int h[maxn];
  int mx[maxn];
  int tin[maxn], timer, et[maxn];
  
  long long x;
  
  pair<int, int> bfs(int src) {
    queue<int> q;
    vector<int> d(n + 1, -1);
    d[src] = 0;
    par[src] = 0;
    q.push(src);
    memset(par, -1, sizeof(par));
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (auto v : g[u]) {
        if (d[v] == -1) {
          d[v] = d[u] + 1;
          par[v] = u;
          q.push(v);
        }
      }
    }
    int mx = *max_element(d.begin(), d.end());
    return make_pair(mx, src);
  }
  
  void dfs(int u) {
    tin[u] = ++timer;
    et[timer] = u;
    for (auto v : adj[u]) {
      h[v] = h[u] + 1;
      dfs(v);
    }
  }
  
  void dfs_mx(int u) {
    mx[u] = 1;
    for (auto v : adj[u]) {
      dfs_mx(v);
      mx[u] = max(mx[u], mx[v] + 1);
    }
  }
  
  bool done;
  
  void traverse(int u) {
    if (done) return;
    if (tin[u] == 60) {
      done = 1;
      return;
    }
//    cerr << "at " << u << " " << tin[u] << endl;
    for (auto v : adj[u]) {
      if (done) return;
      int nxt = Move(v);
      if (nxt) {
        x |= (1ll << (tin[v] - 1));
      }
//      cerr << "Y " << u << " " << v << endl;
      traverse(v);
      if (done) return;
    }
    if (par[u] != -1) {
      Move(par[u]);
//      cerr << "X " << u << " " << par[u] << endl;
    }
  }
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
  pair<int, int> opt = make_pair(-1, -1);
  pair<int, int> mn = make_pair(1e9, 1e9);
  n = N;
  for (int i = 0; i < n; ++i) {
    g[i].clear();
    adj[i].clear();
  }
  for (int i = 0; i < M; ++i) {
    g[A[i]].push_back(B[i]);
    g[B[i]].push_back(A[i]);
  }
  for (int i = 0; i < n; ++i) {
    pair<int, int> cur = bfs(i);
    opt = max(opt, cur);
    mn = min(mn, cur);
  }
  if (opt.first + 1 >= 60) {
    bfs(opt.second);
    for (int i = 0; i < n; ++i) {
      if (par[i] != -1) {
        adj[par[i]].push_back(i);
      }
    }
    timer = 0;
    dfs(opt.second);
    if (h[P] >= 59) {
      x = V;
      for (int i = 1; i < 60; ++i) {
        assert(par[P] != -1);
//        cerr << "E " << P << " " << par[P] << endl;
        x |= (1ll << (Move(par[P])));
        P = par[P];
      }
      return x;
    }
    x = 0;
    while (par[P] != -1) {
      int nxt = Move(par[P]);
      if (par[par[P]] == -1) {
        x = nxt;
      }
      P = par[P];
    }
    dfs_mx(P);
//    cerr << "root " << P << endl;
    for (int i = 0; i < 59; ++i) {
      int v = -1;
      for (auto x : adj[P]) {
        if (v == -1 || mx[x] > mx[v]) v = x;
      }
      if (Move(v)) {
        x |= (1ll << h[v]);
      }
      P = v;
    }
    return x;
  } else {
    bfs(mn.second);
    for (int i = 0; i < n; ++i) {
      if (par[i] != -1) {
        adj[par[i]].push_back(i);
      }
    }
//    cerr << "HELO" << endl;
    timer = 0;
    dfs(mn.second);
    while (par[P] != -1) {
      int nxt = Move(par[P]);
      if (par[par[P]] == -1) {
        x = nxt;
      }
      P = par[P];
    }
//    cerr << "ROOT " << P << endl;
    done = 0;
    traverse(P);
    return x;
  }
}

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