oj.uz

Submission #682527

# Submission time Handle Problem Language Result Execution time Memory
682527 2023-01-16T12:48:52 Z peijar Designated Cities (JOI19_designated_cities) C++17
7 / 100
 254 ms 56788 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);
}

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();

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

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 241 ms 46144 KB Output is correct
3 Correct 254 ms 56344 KB Output is correct
4 Correct 223 ms 46048 KB Output is correct
5 Correct 222 ms 46724 KB Output is correct
6 Correct 221 ms 47664 KB Output is correct
7 Correct 188 ms 46868 KB Output is correct
8 Correct 245 ms 56788 KB Output is correct
9 Correct 139 ms 45924 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 241 ms 46144 KB Output is correct
3 Correct 254 ms 56344 KB Output is correct
4 Correct 223 ms 46048 KB Output is correct
5 Correct 222 ms 46724 KB Output is correct
6 Correct 221 ms 47664 KB Output is correct
7 Correct 188 ms 46868 KB Output is correct
8 Correct 245 ms 56788 KB Output is correct
9 Correct 139 ms 45924 KB Output is correct
10 Incorrect 2 ms 5076 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5076 KB Output isn't correct
2 Halted 0 ms 0 KB -