oj.uz

답안 #682534

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
682534 2023-01-16T13:11:47 Z peijar Designated Cities (JOI19_designated_cities) C++17
16 / 100
 390 ms 92696 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Incorrect 3 ms 5076 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 318 ms 48688 KB Output is correct
3 Correct 361 ms 80840 KB Output is correct
4 Correct 302 ms 48592 KB Output is correct
5 Correct 277 ms 49276 KB Output is correct
6 Correct 317 ms 52432 KB Output is correct
7 Correct 278 ms 50032 KB Output is correct
8 Correct 376 ms 81916 KB Output is correct
9 Correct 197 ms 52592 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 291 ms 48680 KB Output is correct
3 Correct 390 ms 92696 KB Output is correct
4 Correct 290 ms 53692 KB Output is correct
5 Correct 285 ms 55960 KB Output is correct
6 Correct 317 ms 59716 KB Output is correct
7 Correct 216 ms 58956 KB Output is correct
8 Correct 366 ms 75448 KB Output is correct
9 Correct 221 ms 58876 KB Output is correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Incorrect 3 ms 5076 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 318 ms 48688 KB Output is correct
3 Correct 361 ms 80840 KB Output is correct
4 Correct 302 ms 48592 KB Output is correct
5 Correct 277 ms 49276 KB Output is correct
6 Correct 317 ms 52432 KB Output is correct
7 Correct 278 ms 50032 KB Output is correct
8 Correct 376 ms 81916 KB Output is correct
9 Correct 197 ms 52592 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 291 ms 48680 KB Output is correct
12 Correct 390 ms 92696 KB Output is correct
13 Correct 290 ms 53692 KB Output is correct
14 Correct 285 ms 55960 KB Output is correct
15 Correct 317 ms 59716 KB Output is correct
16 Correct 216 ms 58956 KB Output is correct
17 Correct 366 ms 75448 KB Output is correct
18 Correct 221 ms 58876 KB Output is correct
19 Correct 3 ms 5076 KB Output is correct
20 Incorrect 306 ms 54980 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Incorrect 3 ms 5076 KB Output isn't correct
3 Halted 0 ms 0 KB -