oj.uz

Submission #104787

# Submission time Handle Problem Language Result Execution time Memory
104787 2019-04-09T09:18:27 Z IOrtroiii Designated Cities (JOI19_designated_cities) C++14
7 / 100
 417 ms 29332 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;
  ans[2] = 1e18;
  for (int i = 2; i <= n; ++i) {
    ans[2] = min(ans[2], sm[i] - md[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:122:7: warning: unused variable 'rt' [-Wunused-variable]
   int rt = 1;
       ^~
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:144:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &q);
   ~~~~~^~~~~~~~~~
designated_cities.cpp:147: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 Incorrect 6 ms 4992 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 7 ms 4992 KB Output is correct
2 Correct 349 ms 18016 KB Output is correct
3 Correct 393 ms 28792 KB Output is correct
4 Correct 348 ms 17988 KB Output is correct
5 Correct 349 ms 17840 KB Output is correct
6 Correct 364 ms 19628 KB Output is correct
7 Correct 309 ms 17804 KB Output is correct
8 Correct 417 ms 29332 KB Output is correct
9 Correct 217 ms 18308 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 349 ms 18016 KB Output is correct
3 Correct 393 ms 28792 KB Output is correct
4 Correct 348 ms 17988 KB Output is correct
5 Correct 349 ms 17840 KB Output is correct
6 Correct 364 ms 19628 KB Output is correct
7 Correct 309 ms 17804 KB Output is correct
8 Correct 417 ms 29332 KB Output is correct
9 Correct 217 ms 18308 KB Output is correct
10 Incorrect 6 ms 5120 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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