oj.uz

답안 #843426

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
843426 2023-09-04T01:59:34 Z anhduc2701 공장들 (JOI14_factories) C++17
15 / 100
 1813 ms 487696 KB 
#include "factories.h"
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
// #define int long long
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define pii pair<int, ll>
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define vii vector<pii>
#define isz(x) (int)x.size()
using namespace std;

const int mxN = 5e5 + 5;
const ll oo = 1e18;

int n;
vector<vii> G;

vi vtn;
vector<vii> vt;

ll dis[mxN];
pii sparse[19][mxN];
ll timer, ecnt, ap[mxN], dep[mxN], cur[mxN], tin[mxN], tout[mxN];

void dfs(int v, int p)
{
  tin[v] = ++timer;
  dep[v] = dep[p] + 1;
  sparse[0][++ecnt] = {dep[v], v};
  ap[v] = ecnt;

  for (auto &[u, w] : G[v])
  {
    if (u == p)
      continue;
    dis[u] = dis[v] + w;
    // cout << dis[u] <<' ' << u << << '\n';
    dfs(u, v);
    sparse[0][++ecnt] = {dep[v], v};
  }

  tout[v] = ++timer;
}

void build_sparse()
{
  for (int p = 1, i = 1; p << 1 <= ecnt; p <<= 1, ++i)
    for (int j = 1; j <= ecnt - p + 1; ++j)
      sparse[i][j] = min(sparse[i - 1][j], sparse[i - 1][j + p]);
}

bool is_ancestor(int u, int v)
{
  return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int LCA(int u, int v)
{
  int l = ap[u], r = ap[v];
  if (l > r)
    swap(l, r);
  int len = r - l + 1, lg_len = __lg(len);
  return min(sparse[lg_len][l], sparse[lg_len][r - (1 << lg_len) + 1]).ss;
}

void Init(int N, int A[], int B[], int D[])
{
  n = N;
  G.resize(n);
  vt.resize(n);
  for (int i = 0; i < N - 1; ++i)
  {
    G[A[i]].emplace_back(B[i], D[i]);
    G[B[i]].emplace_back(A[i], D[i]);
  }
  dfs(0, 0);

  build_sparse();
}
long long Query(int S, int X[], int T, int Y[])
{
  queue<pii> q;
  for (int i = 0; i < S; ++i)
  {
    cur[X[i]] = 1;
    q.emplace(X[i], 0);
    vtn.emplace_back(X[i]);
  }
  for (int i = 0; i < T; ++i)
  {
    cur[Y[i]] = 2;
    vtn.emplace_back(Y[i]);
  }
  sort(all(vtn));
  vtn.erase(unique(all(vtn)), vtn.end());
  sort(all(vtn), [&](int u, int v)
       { return tin[u] < tin[v]; });
  for (int i = 0; i < S + T - 1; ++i)
  {
    vtn.emplace_back(LCA(vtn[i], vtn[i + 1]));
  }
  sort(all(vtn));
  vtn.erase(unique(all(vtn)), vtn.end());
  sort(all(vtn), [&](int u, int v)
       { return tin[u] < tin[v]; });
  auto add_vt = [&](int u, int v, int w)
  {
    vt[u].emplace_back(v, w);
    vt[v].emplace_back(u, w);
  };
  stack<int> s;
  for (int i = 0; i < isz(vtn); ++i)
  {
    while (not s.empty() && not is_ancestor(s.top(), vtn[i]))
      s.pop();
    if (s.empty())
      s.emplace(vtn[i]);
    else
    {
      // cout << s.top() << ' ' << vtn[i] << ' ' << dis[vtn[i]] - dis[s.top()] << '\n';
      add_vt(s.top(), vtn[i], dis[vtn[i]] - dis[s.top()]);
      s.emplace(vtn[i]);
    }
  }
  ll res = oo;
  auto dfs = [&](auto self, int v, int p) -> vll
  {
    vll cur_dis(2, oo);
    if (cur[v])
      cur_dis[cur[v] - 1] = 0;
    for (auto &[u, w] : G[v])
    {
      if (u == p)
        continue;
      vll tmp = self(self, u, v);
      for (int i = 0; i < 2; ++i)
        cur_dis[i] = min(cur_dis[i], tmp[i] + w);
    }
    res = min(res, accumulate(all(cur_dis), 0LL));
    return cur_dis;
  };
  dfs(dfs, vtn[0], 0);
  for (auto v : vtn)
  {
    vt[v].clear();
  }
  for (int i = 0; i < S; ++i)
  {
    cur[X[i]] = 0;
    vt[X[i]].clear();
  }
  for (int i = 0; i < T; ++i)
  {
    cur[Y[i]] = 0;
    vt[Y[i]].clear();
  }
  vtn.clear();
  return res;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 45656 KB Output is correct
2 Correct 1538 ms 59220 KB Output is correct
3 Correct 1735 ms 59080 KB Output is correct
4 Correct 1718 ms 59096 KB Output is correct
5 Correct 1801 ms 69056 KB Output is correct
6 Correct 1051 ms 68292 KB Output is correct
7 Correct 1736 ms 68528 KB Output is correct
8 Correct 1724 ms 68488 KB Output is correct
9 Correct 1813 ms 69060 KB Output is correct
10 Correct 1045 ms 68524 KB Output is correct
11 Correct 1764 ms 68452 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 45656 KB Output is correct
2 Runtime error 625 ms 487696 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 45656 KB Output is correct
2 Correct 1538 ms 59220 KB Output is correct
3 Correct 1735 ms 59080 KB Output is correct
4 Correct 1718 ms 59096 KB Output is correct
5 Correct 1801 ms 69056 KB Output is correct
6 Correct 1051 ms 68292 KB Output is correct
7 Correct 1736 ms 68528 KB Output is correct
8 Correct 1724 ms 68488 KB Output is correct
9 Correct 1813 ms 69060 KB Output is correct
10 Correct 1045 ms 68524 KB Output is correct
11 Correct 1764 ms 68452 KB Output is correct
12 Correct 12 ms 45656 KB Output is correct
13 Runtime error 625 ms 487696 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -