Submission #280295

#	Time	Username	Problem	Language	Result	Execution time	Memory
280295		Haunted_Cpp	Hotspot (NOI17_hotspot)	C++17	64 / 100	2522 ms	1632 KiB

hotspot

/**
 *  author: Haunted_Cpp
**/
 
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
 
template<typename T> ostream &operator << (ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream &operator << (ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream &operator << (ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
 
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }
 
#ifdef LOCAL
#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#else
#define debug(...) 47
#endif

const int MAX_N = 5000 + 5;
const int MAX_K = 2000 + 5;

vector<vector<int>> g(MAX_N);
vector<long double> ans(MAX_N);

int solve(int node, int target, const vector<vector<int>> &dag, vector<int> &dp) {
  if (node == target) return 1;
  int &res = dp[node];
  if (~res) return res;
  res = 0;
  for (auto to : dag[node]) {
    res += solve(to, target, dag, dp);
  }
  return res;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0); 
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int st, et;
    cin >> st >> et;
    g[st].emplace_back(et);
    g[et].emplace_back(st);
  }
  auto bfs = [&](int source, int sink) {
    queue<int> q;
    vector<int> dist(n, 1e9);
    dist[sink] = 0;
    q.push(sink);
    while(!q.empty()) {
      int node = q.front();
      q.pop();
      for (auto to : g[node]) {
        if (dist[to] > dist[node] + 1) {
          dist[to] = dist[node] + 1;
          q.push(to);
        }
      }
    }
    vector<vector<int>> dag(MAX_N);
    vector<pair<int, int>> add;
    function<void(int)> build_dag = [&](int node) {
      const int cur = dist[node];
      for (auto to : g[node]) {
        if (dist[to] == cur - 1) {
          add.emplace_back(node, to);
          build_dag(to);
        }
      }
    };
    build_dag(source);
    sort(add.begin(), add.end());
    add.erase(unique(add.begin(), add.end()), add.end());
    for (auto to : add) {
      dag[to.first].emplace_back(to.second);
    }
    return dag;
  };
  int k;
  cin >> k;
  while(k--) {
    int source, sink;
    cin >> source >> sink;
    vector<vector<int>> a = bfs(source, sink);
    vector<int> dp_a(MAX_N, -1);
    vector<vector<int>> b = bfs(sink, source);
    vector<int> dp_b(MAX_N, -1);
    const int cnt_shortest = solve(source, sink, a, dp_a);
    if (cnt_shortest == 0) continue;
    for (int i = 0; i < n; i++) {
      int L = solve(i, sink, a, dp_a);
      int R = solve(i, source, b, dp_b);
      ans[i] += (long double)L / (long double)cnt_shortest * (long double)R;
    }
  }
  cout << (max_element(ans.begin(), ans.end()) - ans.begin()) << '\n';
  return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 11 / 11
• Subtask 4: 18 / 18
• Subtask 5: 26 / 26
• Subtask 6: 0 / 36