oj.uz

Submission #104784

# Submission time Handle Problem Language Result Execution time Memory
104784 2019-04-09T09:10:45 Z IOrtroiii Designated Cities (JOI19_designated_cities) C++14
7 / 100
 713 ms 50596 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 Correct 7 ms 5120 KB Output is correct
3 Incorrect 7 ms 5120 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 648 ms 37508 KB Output is correct
3 Correct 645 ms 48348 KB Output is correct
4 Correct 557 ms 37656 KB Output is correct
5 Correct 648 ms 37684 KB Output is correct
6 Correct 666 ms 39236 KB Output is correct
7 Correct 632 ms 37440 KB Output is correct
8 Correct 713 ms 49016 KB Output is correct
9 Correct 552 ms 37996 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 664 ms 37700 KB Output is correct
3 Correct 674 ms 50596 KB Output is correct
4 Correct 613 ms 37624 KB Output is correct
5 Correct 579 ms 37536 KB Output is correct
6 Correct 611 ms 39604 KB Output is correct
7 Incorrect 558 ms 37792 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 Correct 7 ms 5120 KB Output is correct
3 Incorrect 7 ms 5120 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 648 ms 37508 KB Output is correct
3 Correct 645 ms 48348 KB Output is correct
4 Correct 557 ms 37656 KB Output is correct
5 Correct 648 ms 37684 KB Output is correct
6 Correct 666 ms 39236 KB Output is correct
7 Correct 632 ms 37440 KB Output is correct
8 Correct 713 ms 49016 KB Output is correct
9 Correct 552 ms 37996 KB Output is correct
10 Correct 7 ms 5120 KB Output is correct
11 Correct 664 ms 37700 KB Output is correct
12 Correct 674 ms 50596 KB Output is correct
13 Correct 613 ms 37624 KB Output is correct
14 Correct 579 ms 37536 KB Output is correct
15 Correct 611 ms 39604 KB Output is correct
16 Incorrect 558 ms 37792 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 Correct 7 ms 5120 KB Output is correct
3 Incorrect 7 ms 5120 KB Output isn't correct
4 Halted 0 ms 0 KB -