Submission #1037357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037357		juicy	Meetings (JOI19_meetings)	C++17	100 / 100	420 ms	852 KiB

meetings

#include <bits/stdc++.h>

#include "meetings.h"

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int MAX = 2e3;

int sz[MAX];
bool del[MAX];
vector<int> g[MAX];

void add(int u, int v) {
  g[u].push_back(v);
  g[v].push_back(u);
} 

void ers(int u, int v) {
  g[u].erase(find(g[u].begin(), g[u].end(), v));
  g[v].erase(find(g[v].begin(), g[v].end(), u));
}

void split(int p, int u, int z, int x) {
  ers(p, u);
  add(p, z);
  add(z, u);
  if (z != x) {
    add(z, x);
  }
}

void dfs(int u, int p) {
  sz[u] = 1;
  for (int v : g[u]) {
    if (!del[v] && v != p) {
      dfs(v, u);
      sz[u] += sz[v];
    }
  }
}

int findCen(int u, int p, int tot) {
  for (int v : g[u]) {
    if (!del[v] && v != p && sz[v] * 2 > tot) {
      return findCen(v, u, tot);
    }
  }
  return u;
}

void solve(int u, int x) {
  dfs(u, u);
  u = findCen(u, u, sz[u]);
  dfs(u, u);
  del[u] = 1;
  vector<int> cands;
  for (auto v : g[u]) {
    if (!del[v]) {
      cands.push_back(v);
    }
  }
  sort(cands.begin(), cands.end(), [&](int u, int v) {
    return sz[u] > sz[v];
  });
  for (int i = 0; i + 1 < cands.size(); i += 2) {
    int a = cands[i], b = cands[i + 1], z = Query(x, a, b);
    if (z == a || z == b) {
      solve(z, x);
      return;
    }
    if (z ^ u) {
      int y = Query(u, x, a) == u ? b : a;
      split(u, y, z, x);
      return;
    }
  }
  if (cands.size() & 1) {
    int v = cands.back(), z = Query(x, v, u);
    if (z == v) {
      solve(z, x);
      return;
    } else if (z ^ u) {
      split(u, v, z, x);
      return;
    }
  }
  add(u, x);
}

void Solve(int N) {
  add(0, 1);
  for (int i = 2; i < N; ++i) {
    if (!g[i].size()) {
      fill(del, del + N, 0);
      solve(0, i);
    }
  }
  for (int i = 0; i < N; ++i) {
    for (int j : g[i]) {
      if (i < j) {
        Bridge(i, j);
      }
    }
  }
}

Compilation message (stderr)

meetings.cpp: In function 'void solve(int, int)':
meetings.cpp:71:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |   for (int i = 0; i + 1 < cands.size(); i += 2) {
      |                   ~~~~~~^~~~~~~~~~~~~~

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