Submission #1174019

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174019		avighna	Meetings (JOI19_meetings)	C++20	0 / 100	1330 ms	17580 KiB

meetings

#include <bits/stdc++.h>

int Query(int u, int v, int w);
void Bridge(int u, int v);

void Solve(int N) {
  std::vector<std::set<int>> adj(N);
  auto add_edge = [&](int u, int v) {
    if (u != v) {
      adj[u].insert(v);
      adj[v].insert(u);
    }
  };
  std::vector q_lca(N, std::vector<int>(N));
  for (int i = 1; i < N; ++i) {
    for (int j = i + 1; j < N; ++j) {
      int lca = Query(0, i, j);
      add_edge(lca, i);
      add_edge(lca, j);
      q_lca[i][j] = q_lca[j][i] = lca;
    }
  }

  std::vector<int> topsort(N);
  std::vector<bool> vis(N);
  std::function<void(int)> dfs;
  dfs = [&](int node) {
    if (vis[node]) {
      return;
    }
    vis[node] = true;
    for (auto &i : adj[node]) {
      dfs(i);
    }
    topsort.push_back(node);
  };
  dfs(0);
  std::reverse(topsort.begin(), topsort.end());
  std::vector<int> pos(N);
  for (int i = 0; i < N; ++i) {
    pos[topsort[i]] = i;
  }

  std::vector<int> par(N);
  for (int i = 1; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      if (i == j) {
        continue;
      }
      if (q_lca[i][j] == j and pos[j] > pos[par[i]]) {
        par[i] = j;
      }
    }
    if (par[i] > i) {
      std::swap(par[i], i);
    }
    Bridge(par[i], i);
  }
}

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