제출 #682534

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
682534		peijar	Designated Cities (JOI19_designated_cities)	C++17	16 / 100	390 ms	92696 KiB

designated_cities

#include <bits/stdc++.h>
#define int long long
using namespace std;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
  bool first = true;
  string res = "[";
  for (const auto &x : v) {
    if (!first)
      res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << to_string(H);
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

const int MAXN = 1e6;

int iDeb[MAXN], iFin[MAXN], lazy[MAXN];
pair<int, int> seg[MAXN];

void pull(int node) { seg[node] = max(seg[2 * node], seg[2 * node + 1]); }

void build(int node, int l, int r) {
  iDeb[node] = l, iFin[node] = r;
  lazy[node] = 0;
  if (l == r) {
    seg[node] = pair(0, l);
    return;
  }

  int m = (l + r) / 2;
  build(2 * node, l, m);
  build(2 * node + 1, m + 1, r);
}

void push(int node) {
  if (!lazy[node])
    return;
  int x = lazy[node];
  lazy[node] = 0;

  seg[node].first += x;
  if (iDeb[node] < iFin[node]) {
    lazy[2 * node] += x, lazy[2 * node + 1] += x;
  }
}

void rangeAdd(int node, int l, int r, int x) {
  push(node);
  if (iDeb[node] > r or iFin[node] < l)
    return;
  if (l <= iDeb[node] and iFin[node] <= r) {
    lazy[node] = x;
    push(node);
    return;
  }
  rangeAdd(2 * node, l, r, x);
  rangeAdd(2 * node + 1, l, r, x);
  pull(node);
}

const int INF = 1e18;
const int MAX = 2e5;

vector<tuple<int, int, int>> adj[MAX];
int tin[MAX], tout[MAX], par[MAXN];
int costDown[MAXN], costUp[MAXN];
int sol[MAXN];
vector<int> order;
int Time;
int nbSommet;

void dfs(int u, int p) {
  par[u] = p;
  tin[u] = Time++;
  order.push_back(u);
  for (auto [v, down, up] : adj[u])
    if (v != p) {
      costDown[v] = up;
      costUp[v] = down;
      dfs(v, u);
    }
  tout[u] = Time;
}

void solve1() {
  int tot = 0;
  for (int i = 1; i < nbSommet; ++i)
    tot += costDown[i];
  auto Solve = [&](auto rec, int u, int p, int curCost) -> void {
    sol[1] = max(sol[1], curCost + tot);
    for (auto [v, a, b] : adj[u])
      if (v != p)
        rec(rec, v, u, curCost + costUp[v] - costDown[v]);
  };
  Solve(Solve, 0, 0, 0);
}

void solve2() {
  if (nbSommet == 2) {
    sol[2] = 0;
    for (int i = 1; i < nbSommet; ++i)
      sol[2] += costDown[i] + costUp[i];
    return;
  }
  int root = 0;
  while (adj[root].size() == 1)
    ++root;
  dfs(root, root);
  tuple<int, int, int> ret(0, 0, 0);
  int tot = 0;
  for (int i = 0; i < nbSommet; ++i)
    if (i != root)
      tot += costDown[i];

  auto Solve = [&](auto rec, int u, int p, int curDiff,
                   int curDepth) -> pair<int, int> {
    vector<pair<int, int>> choix;
    for (auto [v, a, b] : adj[u])
      if (v != p)
        choix.push_back(rec(rec, v, u, curDiff + costUp[v] - costDown[v],
                            curDepth + costUp[v]));
    sort(choix.rbegin(), choix.rend());
    if (choix.size() > 1) {
      auto [c1, s] = choix[0];
      auto [c2, t] = choix[1];
      ret = max(ret, make_tuple(tot + c1 + c2 - 2 * curDepth + curDiff, s, t));
    }
    if (choix.empty())
      return pair(curDepth, u);
    return choix.front();
  };
  Solve(Solve, root, root, 0, 0);
  auto [s, u, v] = ret;
  dbg(s, u, v);
  sol[2] = s;
}

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  cin >> nbSommet;
  int tot = 0;

  for (int i = 1; i < nbSommet; ++i) {
    int u, v, C, D;
    cin >> u >> v >> C >> D;
    --u, --v;
    adj[u].emplace_back(v, C, D);
    adj[v].emplace_back(u, D, C);
    tot += C + D;
  }

  dfs(0, 0);

  build(1, 0, Time - 1);

  solve1();
  solve2();

  int Q;
  cin >> Q;
  while (Q--) {
    int E;
    cin >> E;
    cout << tot - sol[E] << '\n';
  }
}

• Subtask 1: 0 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44