oj.uz

Submission #104781

# Submission time Handle Problem Language Result Execution time Memory
104781 2019-04-09T09:06:35 Z IOrtroiii Designated Cities (JOI19_designated_cities) C++17
7 / 100
 662 ms 57040 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 200200;

vector< tuple<int, int, int> > g[N];
long long md[N];
long long sm[N];
long long up[N];

void dfs_down(int u,int p) {
  for (auto e : g[u]) {
    int v, wf, wb;
    tie(v, wf, wb) = e;
    if (v == p) continue;
    dfs_down(v, u);
    md[u] = max(md[u], md[v] + wb);
    sm[u] += wf + sm[v];
  }
}

void dfs_up(int u,int p) {
  md[u] = max(md[u], up[u]);
  pair<long long, long long> mx(up[u], 0);
  for (auto e : g[u]) {
    int v, wf, wb;
    tie(v, wf, wb) = e;
    if (v == p) continue;
    long long nw = md[v] + wb;
    if (nw > mx.second) {
      mx.second = nw;
    }
    if (mx.first < mx.second) {
      swap(mx.first, mx.second);
    }
  }
  for (auto e : g[u]){
    int v, wf, wb;
    tie(v, wf, wb) = e;
    if (v == p) continue;
    long long nw = md[v] + wb;
    up[v] = wf + (nw == mx.first ? mx.second : mx.first);
    sm[v] = sm[u] + wb - wf;
    dfs_up(v, u);
  }
}

int ver[N], tin[N], tout[N], tt;
int par[N];
int parw[N];
long long d[N];

void dfs(int u,int p) {
  ver[tin[u] = ++tt] = u;
  for (auto e : g[u]) {
    int v, wf, wb;
    tie(v, wf, wb) = e;
    if (v == p) continue;
    par[v] = u;
    parw[v] = wf;
    d[v] = d[u] + wf;
    dfs(v, u);
  }
  tout[u] = tt;
}

pair<long long, int> t[N << 2];
long long lz[N << 2];

void build(int v,int l,int r) {
  if (l == r) {
    t[v] = {d[ver[l]], ver[l]};
    return;
  }
  int md = (l + r) >> 1;
  build(v << 1, l, md);
  build(v << 1 | 1, md + 1, r);
  t[v] = max(t[v << 1], t[v << 1 | 1]);
}

void push(int v,int l,int r) {
  if (lz[v]) {
    t[v].first += lz[v];
    if (l < r) {
      lz[v << 1] += lz[v];
      lz[v << 1 | 1] += lz[v];
    }
    lz[v] = 0;
  }
}

void add(int v,int l,int r,int L,int R,int val) {
  push(v, l, r);
  if (L > r || R < l) return;
  if (L <= l && r <= R) {
    lz[v] += val;
    push(v, l, r);
    return;
  }
  int md = (l + r) >> 1;
  add(v << 1, l, md, L, R, val);
  add(v << 1 | 1, md + 1, r, L, R, val);
  t[v] = max(t[v << 1], t[v << 1 | 1]);
}

bool visit[N];
long long ans[N];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i < n; ++i) {
    int u, v, x, y;
    scanf("%d %d %d %d", &u, &v, &x, &y);
    g[u].push_back(make_tuple(v, x, y));
    g[v].push_back(make_tuple(u, y, x));
  }
  dfs_down(1, -1);
  dfs_up(1, -1);
  ans[1] = *min_element(sm + 1, sm + 1 + n);
  int rt = 1;
  for (int i = 2; i <= n; ++i) {
    if (sm[i] - md[i] < sm[rt] - md[rt]) rt = i;
  }
  dfs(rt, -1);
  build(1, 1, n);
  visit[rt] = true;
  long long now = sm[rt];
  for (int i = 2; i <= n; ++i) {
    now -= t[1].first;
    ans[i] = now;
    int v = t[1].second;
    while (!visit[v]) {
      visit[v] = true;
      add(1, 1, n, tin[v], tout[v], parw[v]);
      v = par[v];
    }
  }
  int q;
  scanf("%d", &q);
  while (q--) {
    int v;
    scanf("%d", &v);
    printf("%lld\n", ans[v]);
  }
}

Compilation message

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
designated_cities.cpp:115:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d", &u, &v, &x, &y);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:141:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &q);
   ~~~~~^~~~~~~~~~
designated_cities.cpp:144:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &v);
     ~~~~~^~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5120 KB Output is correct
2 Incorrect 9 ms 5120 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 8 ms 5120 KB Output is correct
2 Correct 476 ms 41052 KB Output is correct
3 Correct 637 ms 54844 KB Output is correct
4 Correct 402 ms 39036 KB Output is correct
5 Correct 427 ms 39728 KB Output is correct
6 Correct 482 ms 45864 KB Output is correct
7 Correct 395 ms 39728 KB Output is correct
8 Correct 662 ms 55456 KB Output is correct
9 Correct 269 ms 40228 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5120 KB Output is correct
2 Correct 462 ms 40800 KB Output is correct
3 Correct 659 ms 57040 KB Output is correct
4 Correct 420 ms 38576 KB Output is correct
5 Correct 448 ms 39860 KB Output is correct
6 Correct 501 ms 45976 KB Output is correct
7 Incorrect 315 ms 39972 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5120 KB Output is correct
2 Correct 476 ms 41052 KB Output is correct
3 Correct 637 ms 54844 KB Output is correct
4 Correct 402 ms 39036 KB Output is correct
5 Correct 427 ms 39728 KB Output is correct
6 Correct 482 ms 45864 KB Output is correct
7 Correct 395 ms 39728 KB Output is correct
8 Correct 662 ms 55456 KB Output is correct
9 Correct 269 ms 40228 KB Output is correct
10 Correct 8 ms 5120 KB Output is correct
11 Correct 462 ms 40800 KB Output is correct
12 Correct 659 ms 57040 KB Output is correct
13 Correct 420 ms 38576 KB Output is correct
14 Correct 448 ms 39860 KB Output is correct
15 Correct 501 ms 45976 KB Output is correct
16 Incorrect 315 ms 39972 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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