oj.uz

Submission #1014621

# Submission time Handle Problem Language Result Execution time Memory
1014621 2024-07-05T08:21:56 Z adrielcp Factories (JOI14_factories) C++17
0 / 100
 8000 ms 146392 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define debug(x) cout << #x << " " << x << endl;

#define ll long long
const ll INF = 1e18;
#define info pair<ll,ll>
vector<vector<info>> adj;
vector<vector<int>> up;
vector<ll> dist;
vector<int> tin, tout;
int n;
bool is_ancestor(int u, int v)
{
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v)
{
    if (is_ancestor(u, v))
        return u;
    if (is_ancestor(v, u))
        return v;
    for (int i = 31; i >= 0; --i) {
        if (!is_ancestor(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}

void Init(int N, int A[], int B[], int D[]) {
  n = N;
  adj = vector<vector<info>>(n, vector<info>());
  up = vector<vector<int>>(n, vector<int>(32));
  dist = vector<ll>(n); // dist from root
  tin =vector<int>(n);
  tout = vector<int>(n);
  for (int i = 0; i < n-1; i++) {
    adj[A[i]].push_back({B[i], D[i]});
    adj[B[i]].push_back({A[i], D[i]});
  }

  int timer = 0;
  function<void(int, int, int)> dfs = [&](int node, int par, int cost) {
    dist[node] = cost;

    tin[node] = ++timer;
    up[node][0] = par;
    for (int j = 1; j < 31; j++) up[node][j] = up[up[node][j-1]][j-1]; 

    for (auto [children,w] : adj[node]) {
      if (children != par) {
        dfs(children, node, cost+w);
      }
    }
    tout[node] = ++timer;
  };

  dfs(0, 0, 0);
}

long long Query(int s, int X[], int t, int Y[]) {
  ll ans = INF;

  for (int i = 0; i < s; i++) for (int j = 0 ; j < t; j++) {
    int a = X[i], b = Y[j];
    // ans = min(ans, dist[a] + dist[b] - 2*dist[lca(a, b)]);
    // cout << "a: " << a << ", b: " << b << endl; 
    // debug(dist[a]);
    // debug(dist[b]);
    // debug(lca(a, b));
    // cout << dist[a] + dist[b] - 2*dist[(lca(a, b))] << endl;
    ans = min(ans, dist[a] + dist[b] - 2*dist[(lca(a, b))]);
  }

  // cout << "ans: " << ans << endl;
  return ans;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 600 KB Output is correct
2 Execution timed out 8050 ms 9524 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 943 ms 140568 KB Output is correct
3 Incorrect 2702 ms 146392 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 600 KB Output is correct
2 Execution timed out 8050 ms 9524 KB Time limit exceeded
3 Halted 0 ms 0 KB -