Submission #280310

#	Time	Username	Problem	Language	Result	Execution time	Memory
280310		Haunted_Cpp	Hotspot (NOI17_hotspot)	C++17	100 / 100	1692 ms	1596 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<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);
  }
  vector<vector<int>> a, b;
  auto bfs = [&](int source, int sink) {
    a.clear();
    b.clear();
    a.resize(MAX_N);
    b.resize(MAX_N);
    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);
        }
      }
    }
    function<void(int)> build_dag = [&](int node) {
      const int cur = dist[node];
      for (auto to : g[node]) {
        if (dist[to] == cur - 1) {
          a[node].emplace_back(to);
          b[to].emplace_back(node);
          build_dag(to);
        }
      }
    };
    build_dag(source);
    for (int i = 0; i < MAX_N; i++) {
      sort(a[i].begin(), a[i].end());
      sort(b[i].begin(), b[i].end());
      a[i].erase(unique(a[i].begin(), a[i].end()), a[i].end());
      b[i].erase(unique(b[i].begin(), b[i].end()), b[i].end());
    }
  };
  int k;
  cin >> k;
  vector<int> dp_a, dp_b;
  while(k--) {
    int source, sink;
    cin >> source >> sink;
    bfs(source, sink);
    dp_a = dp_b = vector<int>(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] += 1.0 * L / cnt_shortest * 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: 36 / 36