oj.uz

Submission #104790

# Submission time Handle Problem Language Result Execution time Memory
104790 2019-04-09T09:21:03 Z IOrtroiii Designated Cities (JOI19_designated_cities) C++14
16 / 100
 436 ms 32004 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] + wf);
    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] + wf;
    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] + wf;
    up[v] = wb + (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 Correct 6 ms 4992 KB Output is correct
2 Incorrect 7 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 4992 KB Output is correct
2 Correct 392 ms 18012 KB Output is correct
3 Correct 412 ms 28676 KB Output is correct
4 Correct 364 ms 17928 KB Output is correct
5 Correct 388 ms 17832 KB Output is correct
6 Correct 410 ms 19756 KB Output is correct
7 Correct 300 ms 17796 KB Output is correct
8 Correct 394 ms 29364 KB Output is correct
9 Correct 299 ms 18316 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5092 KB Output is correct
2 Correct 389 ms 17984 KB Output is correct
3 Correct 436 ms 30888 KB Output is correct
4 Correct 366 ms 18016 KB Output is correct
5 Correct 335 ms 17832 KB Output is correct
6 Correct 404 ms 20040 KB Output is correct
7 Correct 270 ms 18184 KB Output is correct
8 Correct 381 ms 32004 KB Output is correct
9 Correct 218 ms 24480 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Incorrect 7 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 4992 KB Output is correct
2 Correct 392 ms 18012 KB Output is correct
3 Correct 412 ms 28676 KB Output is correct
4 Correct 364 ms 17928 KB Output is correct
5 Correct 388 ms 17832 KB Output is correct
6 Correct 410 ms 19756 KB Output is correct
7 Correct 300 ms 17796 KB Output is correct
8 Correct 394 ms 29364 KB Output is correct
9 Correct 299 ms 18316 KB Output is correct
10 Correct 7 ms 5092 KB Output is correct
11 Correct 389 ms 17984 KB Output is correct
12 Correct 436 ms 30888 KB Output is correct
13 Correct 366 ms 18016 KB Output is correct
14 Correct 335 ms 17832 KB Output is correct
15 Correct 404 ms 20040 KB Output is correct
16 Correct 270 ms 18184 KB Output is correct
17 Correct 381 ms 32004 KB Output is correct
18 Correct 218 ms 24480 KB Output is correct
19 Correct 7 ms 4992 KB Output is correct
20 Incorrect 376 ms 24480 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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