oj.uz

Submission #280281

# Submission time Handle Problem Language Result Execution time Memory
280281 2020-08-22T15:28:16 Z Haunted_Cpp Hotspot (NOI17_hotspot) C++17
0 / 100
 2 ms 896 KB 
/**
 *  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);
    function<void(int)> build_dag = [&](int node) {
      const int cur = dist[node];
      for (auto to : g[node]) {
        if (dist[to] == cur - 1) {
          dag[node].emplace_back(to);
          build_dag(to);
        }
      }
    };
    build_dag(source);
    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;
    }
  }
  for (int i = 0; i < n; i++) cout << ans[i] << '\n';
  cout << (max_element(ans.begin(), ans.end()) - ans.begin()) << '\n';
  return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -