oj.uz

Submission #897379

# Submission time Handle Problem Language Result Execution time Memory
897379 2024-01-03T02:58:15 Z NeroZein Designated Cities (JOI19_designated_cities) C++17
16 / 100
 244 ms 47444 KB 
#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int N = 2e5 + 5;

int n;
int cnt;
int euler[N];
bool active[N];
long long f[N];
long long ans[N];
int in[N], out[N];
long long dist[N];
pair<int, int> pr[N];
long long seg[N * 2];
long long lazy[N * 2];
vector<pair<int, int>> g[N];
pair<long long, long long> dp[N];

void dfs1(int v, int p) {
  long long mx = 0, mx2 = 0;
  for (auto [u, w] : g[v]) {
    if (u == p) continue;
    dist[1] += w;
    dfs1(u, v); 
    mx2 = max(mx2, dp[u].first + w); 
    if (mx2 > mx) swap(mx, mx2);
  }
  dp[v] = make_pair(mx, mx2);
}

void dfs2(int v, int p, long long up) {
  auto [mx, mx2] = dp[v];
  for (auto [u, w] : g[v]) {
    if (u == p) {
      dist[v] += w;
      up += w; 
    }
  }
  f[v] = max(mx, up);
  for (auto [u, w] : g[v]) {
    if (u == p) continue;
    dist[u] = dist[v] - w; 
    long long nup = (mx == dp[u].first + w ? mx2 : mx);
    nup = max(up, nup);
    dfs2(u, v, nup);
  }
}

void push(int nd, int l, int r) {
  if (!lazy[nd]) return;
  seg[nd] += lazy[nd];
  if (l != r) {
    int mid = (l + r) >> 1;
    int rs = nd + ((mid - l + 1) << 1);
    lazy[nd + 1] += lazy[nd];
    lazy[rs] += lazy[nd];    
  }
  lazy[nd] = 0; 
}

void upd(int nd, int l, int r, int s, int e, int v) {
  push(nd, l, r);
  if (l >= s && r <= e) {
    lazy[nd] = v; 
    push(nd, l, r);
    return;
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (mid >= e) {
    push(rs, mid + 1, r);
    upd(nd + 1, l, mid, s, e, v); 
  } else {
    if (mid < s) {
      push(nd + 1, l, mid);
      upd(rs, mid + 1, r, s, e, v); 
    } else {
      upd(nd + 1, l, mid, s, e, v);
      upd(rs, mid + 1, r, s, e, v);       
    }
  }
  seg[nd] = max(seg[nd + 1], seg[rs]); 
}

int get(int nd, int l, int r) {
  push(nd, l, r); 
  if (l == r) {
    return euler[l]; 
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  push(nd + 1, l, mid);
  push(rs, mid + 1, r); 
  if (seg[nd + 1] > seg[rs]) {
    return get(nd + 1, l, mid);
  }
  return get(rs, mid + 1, r); 
}

bool dfs3(int v, int p, int o) {
  euler[cnt] = v; 
  in[v] = cnt++;
  bool ret = o == v;
  for (auto [u, w] : g[v]) {
    if (u == p) continue;
    pr[u] = make_pair(v, w);
    bool ru = dfs3(u, v, o);
    if (!ru) {
      upd(0, 0, n - 1, in[u], out[u], w);
    } else {
      ret = true;
    }
  }
  out[v] = cnt - 1;
  active[v] = ret;
  return ret; 
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n;
  for (int i = 1; i < n; ++i) {
    int u, v, c, d;
    cin >> u >> v >> c >> d;
    g[u].emplace_back(v, c);
    g[v].emplace_back(u, d); 
  }
  dfs1(1, 0);
  dfs2(1, 0, 0);
  ans[1] = *min_element(dist + 1, dist + 1 + n);
  ans[2] = LLONG_MAX;
  dist[0] = LLONG_MAX;
  int r = 0, o = 0; 
  for (int i = 1; i <= n; ++i) {
    if (dist[i] - f[i] < dist[r] - f[r]) {
      r = i;
    } else if (dist[i] - f[i] == dist[r] - f[r]) {
      o = i;
    }
  }
  ans[2] = dist[r] - f[r];
  dfs3(r, r, o);
  //for (int i = 3; i <= n; ++i) {
    //ans[i] = ans[i - 1] - seg[0];
    //int v = get(0, 0, n - 1);
    //while (!active[v]) {
      //auto [pv, pw] = pr[v];
      //upd(0, 0, n - 1, in[v], out[v], -pw);
      //v = pv; 
    //}
  //}
  int q;
  cin >> q;
  while (q--) {
    int e;
    cin >> e;
    cout << ans[e] << '\n'; 
  }
  return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16732 KB Output is correct
2 Incorrect 3 ms 18780 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16732 KB Output is correct
2 Correct 189 ms 30544 KB Output is correct
3 Correct 179 ms 44116 KB Output is correct
4 Correct 187 ms 30448 KB Output is correct
5 Correct 184 ms 30444 KB Output is correct
6 Correct 195 ms 32740 KB Output is correct
7 Correct 160 ms 30508 KB Output is correct
8 Correct 197 ms 47444 KB Output is correct
9 Correct 145 ms 31164 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Correct 244 ms 30848 KB Output is correct
3 Correct 199 ms 44116 KB Output is correct
4 Correct 189 ms 30600 KB Output is correct
5 Correct 233 ms 30640 KB Output is correct
6 Correct 193 ms 33620 KB Output is correct
7 Correct 144 ms 30912 KB Output is correct
8 Correct 229 ms 42096 KB Output is correct
9 Correct 129 ms 31084 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16732 KB Output is correct
2 Incorrect 3 ms 18780 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16732 KB Output is correct
2 Correct 189 ms 30544 KB Output is correct
3 Correct 179 ms 44116 KB Output is correct
4 Correct 187 ms 30448 KB Output is correct
5 Correct 184 ms 30444 KB Output is correct
6 Correct 195 ms 32740 KB Output is correct
7 Correct 160 ms 30508 KB Output is correct
8 Correct 197 ms 47444 KB Output is correct
9 Correct 145 ms 31164 KB Output is correct
10 Correct 3 ms 16732 KB Output is correct
11 Correct 244 ms 30848 KB Output is correct
12 Correct 199 ms 44116 KB Output is correct
13 Correct 189 ms 30600 KB Output is correct
14 Correct 233 ms 30640 KB Output is correct
15 Correct 193 ms 33620 KB Output is correct
16 Correct 144 ms 30912 KB Output is correct
17 Correct 229 ms 42096 KB Output is correct
18 Correct 129 ms 31084 KB Output is correct
19 Correct 2 ms 16728 KB Output is correct
20 Incorrect 193 ms 30452 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16732 KB Output is correct
2 Incorrect 3 ms 18780 KB Output isn't correct
3 Halted 0 ms 0 KB -