oj.uz

Submission #897374

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

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

const int N = 2e5 + 5;

long long f[N];
long long ans[N];
long long dist[N];
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);
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  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; 
  for (int i = 1; i <= n; ++i) {
    if (dist[i] - f[i] < dist[r] - f[r]) {
      r = i;
    }
  }
  ans[2] = dist[r] - f[r];
  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 10588 KB Output is correct
2 Incorrect 2 ms 10588 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 10600 KB Output is correct
2 Correct 135 ms 26476 KB Output is correct
3 Correct 188 ms 40828 KB Output is correct
4 Correct 142 ms 25252 KB Output is correct
5 Correct 124 ms 26568 KB Output is correct
6 Correct 127 ms 28880 KB Output is correct
7 Correct 98 ms 26564 KB Output is correct
8 Correct 183 ms 41300 KB Output is correct
9 Correct 111 ms 27460 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10708 KB Output is correct
2 Correct 169 ms 26512 KB Output is correct
3 Correct 156 ms 43312 KB Output is correct
4 Correct 147 ms 25212 KB Output is correct
5 Correct 142 ms 26624 KB Output is correct
6 Correct 137 ms 29088 KB Output is correct
7 Correct 83 ms 26820 KB Output is correct
8 Correct 139 ms 35920 KB Output is correct
9 Correct 93 ms 26812 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Incorrect 2 ms 10588 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 10600 KB Output is correct
2 Correct 135 ms 26476 KB Output is correct
3 Correct 188 ms 40828 KB Output is correct
4 Correct 142 ms 25252 KB Output is correct
5 Correct 124 ms 26568 KB Output is correct
6 Correct 127 ms 28880 KB Output is correct
7 Correct 98 ms 26564 KB Output is correct
8 Correct 183 ms 41300 KB Output is correct
9 Correct 111 ms 27460 KB Output is correct
10 Correct 2 ms 10708 KB Output is correct
11 Correct 169 ms 26512 KB Output is correct
12 Correct 156 ms 43312 KB Output is correct
13 Correct 147 ms 25212 KB Output is correct
14 Correct 142 ms 26624 KB Output is correct
15 Correct 137 ms 29088 KB Output is correct
16 Correct 83 ms 26820 KB Output is correct
17 Correct 139 ms 35920 KB Output is correct
18 Correct 93 ms 26812 KB Output is correct
19 Correct 2 ms 10588 KB Output is correct
20 Incorrect 150 ms 26612 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 10588 KB Output is correct
2 Incorrect 2 ms 10588 KB Output isn't correct
3 Halted 0 ms 0 KB -