Submission #1043789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043789		abczz	Meetings (JOI19_meetings)	C++17	100 / 100	469 ms	1396 KiB

meetings

#include "meetings.h"
#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <array>
#define ll long long

using namespace std;

bool C[2000], B[2000];
ll sz[2000], tot, node_cnt;
unordered_map <ll, ll> adj[2000];

void add_edge(ll u, ll v) {
  node_cnt += (ll)(B[u] ^ 1) + (ll)(B[v] ^ 1);
  B[u] = B[v] = 1;
  adj[u][v] = adj[v][u] = 1;
}
void del_edge(ll u, ll v) {
  adj[u].erase(v);
  adj[v].erase(u);
}
void ins(ll u, ll v, ll x) {
  del_edge(u, v);
  add_edge(u, x);
  add_edge(x, v);
}
ll find_centroid(ll u, ll p, ll w) {
  sz[u] = 1;
  ll mx = -1, res = -1;
  for (auto [v, x] : adj[u]) {
    if (!C[v] && v != p) {
      res = max(res, find_centroid(v, u, w));
      sz[u] += sz[v];
      mx = max(mx, sz[v]);
    }
  }
  mx = max(mx, w-sz[u]);
  if (mx <= w/2) return u;
  else return res;
}

void dfs_sz(ll u, ll p) {
  sz[u] = 1;
  for (auto [v, x] : adj[u]) {
    if (!C[v] && v != p) {
      dfs_sz(v, u);
      sz[u] += sz[v];
    }
  }
}

void solve(ll u, ll w) {
  ll c = find_centroid(u, -1, w);
  dfs_sz(c, -1);
  C[c] = 1;
  vector <array<ll, 2>> V;
  for (auto [v, x] : adj[c]) {
    if (!C[v]) {
      V.push_back({sz[v], v});
    }
  }
  sort(V.begin(), V.end());
  while (!V.empty()) {
    if (V.size() > 1) {
      auto [x, a] = V.back();
      V.pop_back();
      auto [y, b] = V.back();
      V.pop_back();
      ll z = Query(a, b, tot);
      if (z == a) {
        solve(a, sz[a]);
        return;
      }
      else if (z == b) {
        solve(b, sz[b]);
        return;
      }
      else if (z == tot) {
        ll tmp = Query(a, tot, c);
        if (tmp == tot) ins(a, c, tot);
        else ins(b, c, tot);
        return;
      }
      else if (z != c) {
        ll tmp = Query(a, tot, c);
        if (tmp == z) {
          ins(a, c, z);
          add_edge(z, tot);
        }
        else {
          ins(b, c, z);
          add_edge(z, tot);
        }
        return;
      }
    }
    else {
      auto [x, a] = V.back();
      V.pop_back();
      ll z = Query(a, c, tot);
      if (z == tot) ins(a, c, tot);
      else if (z == a) solve(a, sz[a]);
      else if (z != c) {
        ins(a, c, z);
        add_edge(z, tot);
      }
      else add_edge(c, tot);
      return;
    }
  }
  add_edge(c, tot);
}
void Solve(int N) {
  for (int i=0; i<N; ++i) {
    B[i] = 0;
    adj[i].clear();
  }
  ll x = Query(0, 1, 2);
  for (int i=0; i<=2; ++i) {
    if (i == x) continue;
    add_edge(i, x);
  }
  for (int i=3; i<N; ++i) {
    if (B[i]) continue;
    tot = i;
    for (int j=0; j<N; ++j) {
      C[j] = 0;
    }
    solve(0, node_cnt);
  }
  for (int i=0; i<N; ++i) {
    for (auto [v, x] : adj[i]) {
      if (i > v) continue;
      Bridge(i, v);
    }
  }
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 71 / 71