fork download
copy 
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cassert>
  4. #include <cstring>
  5. #include <iostream>
  6. #include <cmath>
  7. #include <deque>
  8. #include <queue>
  9. #include <stack>
  10. #include <vector>
  11. #include <algorithm>
  12. #include <set>
  13. #include <map>
  14. #include <complex>
  15.  
  16. #define mp(a, b) make_pair((a), (b))
  17. #define pb(a) push_back((a))
  18. #define pf(a) push_front((a))
  19. #define rb() pop_back()
  20. #define rf() pop_front()
  21. #define sz(a) ((int)a.size())
  22.  
  23. using namespace std;
  24.  
  25. typedef long long lld;
  26. typedef pair<int, int> pii;
  27. typedef pair<lld, lld> pll;
  28. typedef pair<lld, int> pli;
  29. typedef pair<int, lld> pil;
  30. typedef vector<vector<int>> Matrix;
  31. typedef vector<vector<int>> Adj;
  32. typedef vector<int> Row;
  33. typedef complex<double> Complex;
  34. typedef vector<Complex> Vcomplex;
  35.  
  36. const int MOD = 1e9 + 7;
  37. const int INF = 1e9;
  38. const lld LINF = 1e18;
  39. const double FINF = 1e15;
  40. const double EPS = 1e-9;
  41. const double PI = 2.0 * acos(0.0);
  42.  
  43. const int M = 19;
  44.  
  45. int n, m;
  46. int c[505];
  47. vector<int> g[505];
  48. vector<int> g2[250005];
  49. int par[250005][25];
  50. int p[250005];
  51. int cost[250005][25];
  52. int depth[250005];
  53.  
  54. inline int encode(int i, int j) {
  55.   return i * n + j;
  56. }
  57.  
  58. int max_cost(int u, int v) {
  59.   if (depth[u] < depth[v]) swap(u, v);
  60.   int ret = 0;
  61.   int d = depth[u] - depth[v];
  62.   for (int i = 0; i < M; ++i) {
  63.     if (d&1<<i) {
  64.       ret = max(ret, cost[u][i]);
  65.       u = par[u][i];
  66.     }
  67.   }
  68.  
  69.   if (u == v) return ret;
  70.   for (int i = M - 1; i >= 0; --i) {
  71.     if (par[u][i] != par[v][i]) {
  72.       ret = max(ret, cost[u][i]);
  73.       ret = max(ret, cost[v][i]);
  74.       u = par[u][i];
  75.       v = par[v][i];
  76.     }
  77.   }
  78.   return max(ret, max(cost[u][0], cost[v][0]));
  79. }
  80.  
  81. void dfs(int cur) {
  82.   for (auto nxt : g2[cur]) {
  83.     if (nxt != par[cur][0]) {
  84.       depth[nxt] = depth[cur] + 1;
  85.       par[nxt][0] = cur;
  86.       cost[nxt][0] = max(cost[nxt][0], c[cur/n] * c[cur%n]);
  87.       dfs(nxt);
  88.     }
  89.   }
  90. }
  91.  
  92. int f(int x) {
  93.   return p[x] = (x == p[x] ? x : f(p[x]));
  94. }
  95.  
  96. int main() {
  97.   scanf("%d %d", &n, &m);
  98.   for (int i = 0; i < n; ++i) scanf("%d", &c[i]);
  99.   for (int i = 0; i < m; ++i) {
  100.     int u, v;
  101.     scanf("%d %d", &u, &v);
  102.     --u, --v;
  103.     g[u].pb(v);
  104.     g[v].pb(u);
  105.   }
  106.   vector<pii> V;
  107.   for (int i = 0; i < n; ++i) {
  108.     for (int j = 0; j < n; ++j) {
  109.       cost[encode(i, j)][0] = c[i] * c[j];
  110.       V.emplace_back(c[i] * c[j], encode(i, j));
  111.     }
  112.   }
  113.   for (int i = 0; i < n * n; ++i) p[i] = i;
  114.   sort(V.begin(), V.end());
  115.   for (pii vv : V) {
  116.     int u = vv.second / n;
  117.     int v = vv.second % n;
  118.     for (int nxt : g[u]) {
  119.       int en = encode(nxt, v);
  120.       if (c[nxt] * c[v] <= c[u] * c[v]) {
  121.         int cp = f(vv.second);
  122.         int np = f(en);
  123.         if (cp != np) {
  124.           p[cp] = np;
  125.           g2[vv.second].pb(en);
  126.           g2[en].pb(vv.second);
  127.         }
  128.       }
  129.     }
  130.     for (int nxt : g[v]) {
  131.       int en = encode(u, nxt);
  132.       if (c[u] * c[nxt] <= c[u] * c[v]) {
  133.         int cp = f(vv.second);
  134.         int np = f(en);
  135.         if (cp != np) {
  136.           p[cp] = np;
  137.           g2[vv.second].pb(en);
  138.           g2[en].pb(vv.second);
  139.         }
  140.       }
  141.     }
  142.   }
  143.   dfs(0);
  144.   for (int i = 0; i < M - 1; ++i) {
  145.     for (int j = 0; j < n * n; ++j) {
  146.       par[j][i+1] = par[par[j][i]][i];
  147.       cost[j][i+1] = max(cost[j][i], cost[par[j][i]][i]);
  148.     }
  149.   }
  150.   int q;
  151.   scanf("%d", &q);
  152.   for (int i = 0; i < q; ++i) {
  153.     int u, v;
  154.     scanf("%d %d", &u, &v);
  155.     --u, --v;
  156.     printf("%d\n", max_cost(encode(u, v), encode(v, u)));
  157.   }
  158. }
Success #stdin #stdout 0s 71872KB
comments (?)
stdin
copy 
5 5
5 1 3 100 12
1 2
2 3
3 1
4 3
4 5
3
1 2
2 3
5 3
stdout
copy 
5
3
100
https://ideone.com/eBn2sQ
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!