제출 #1174061

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1174061		avighna	Meetings (JOI19_meetings)	C++20	29 / 100	1328 ms	17020 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);
    }
  };
  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;
  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);
  };
  for (int i = 1; i < N; ++i) {
    dfs(i);
  }
  if (std::find(topsort.begin(), topsort.end(), 0) == topsort.end()) {
    topsort.push_back(0);
  }
  std::reverse(topsort.begin(), topsort.end());
  std::vector<int> pos(N);
  for (int i = 0; i < N; ++i) {
    pos[topsort[i]] = i;
  }

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

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