oj.uz

Submission #107407

# Submission time Handle Problem Language Result Execution time Memory
107407 2019-04-24T05:56:07 Z shoemakerjo Designated Cities (JOI19_designated_cities) C++14
16 / 100
 582 ms 40952 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const int maxn = 200010;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pil pair<int, pll>
#define pli pair<ll, int>
#define mp make_pair

int n, q;

ll seg[maxn*4]; //a max seg tree

//we want the seg-tree to go in euler tour order
int qus[maxn];
vector<pil> adj[maxn];

ll ans[maxn]; //store ans for each value
ll dep[maxn]; //distance from root to me
int par[maxn];
ll plink[maxn];

int rt; //some global root variable
ll esum = 0LL; //total edge sum
//barebones dfs
void dfs(int u, int p = -1) {
  if (p == -1) {
    dep[u] = 0LL;
    par[u] = -1;
  }
  for (pil vp : adj[u]) {
    if (vp.first == p) continue;
    dep[vp.first] = dep[u] + vp.second.first; //dep is length to bot
    par[vp.first] = u;
    plink[vp.first] = vp.second.second;
    dfs(vp.first, u);
  }
}

void dfs1(int u, ll msum = 0LL) {
  ans[1] = min(ans[1], esum - msum);
  for (pil vp : adj[u]) {
    if (vp.first != par[u]) {
      dfs1(vp.first, msum - vp.second.second +
        vp.second.first);
    }
  }
}

void go1() {
  //finds the answer for 1 by itself
  //when I go to a child, I reverse that edge
  //start with all going down
  ans[1] = esum;
  ll csum = 0LL;
  for (int i = 1; i <= n; i++) {
    if (i != rt) csum += plink[i];
  }
  dfs1(rt, csum);
}

pli mdepth[maxn]; //want maxdepth

pii cg;

void dfs2(int u, ll msum) {
  //msum is the sum of everything in
  //consider me to be an lca
  mdepth[u] = {dep[u], u};
  vector<pli> ops;

  for (pil vp : adj[u]) {
    if (vp.first == par[u]) continue;
    dfs2(vp.first, msum - vp.second.second);
    ops.push_back(mdepth[vp.first]);
  }

  sort(ops.begin(), ops.end());
  reverse(ops.begin(), ops.end());
  if (ops.size()) mdepth[u] = ops[0];
  if (ops.size() < 2) return;
  msum += ops[0].first + ops[1].first - dep[u];
  if (esum - msum < ans[2]) {
    ans[2] = esum - msum;
    cg = mp(ops[0].second, ops[1].second);
  }
}

pii go2() {
  //we  consider everything as the lca
  //then we sacrifice a certain amount that "goes down"
  //start with all of the par-links in (par points up)
  ans[2] = esum;
  //   we lose some of the par-links
  ll csum = 0LL;
  for (int i = 1; i <= n; i++) {
    if (i != rt) csum += plink[i];
  }
  dfs2(rt, csum);
  return cg;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n;
  int a, b;
  ll c, d;
  for (int i = 0; i < n-1; i++) {
    cin >> a >> b >> c >> d;
    adj[a].emplace_back(b, mp(c, d));
    adj[b].emplace_back(a, mp(d, c));
    esum += c;
    esum += d;
  }
  cin >> q;
  for (int i = 1; i <= q; i++) {
    cin >> qus[i];
  }
  if (n == 2) {
    //just bash
    for (int i = 1; i <= q; i++) {
      if (qus[i] == 2) {
        cout << 0 << endl;
      }
      else {
        cout << min(adj[1][0].second.first,
          adj[1][0].second.second);
      }
    }
    return 0;
  }

  //now we want to root at a non-leaf
  rt = 1;
  for (int i = 2; i <= n; i++) {
    if (adj[i].size() != 1) rt = i;
  }
  dfs(rt);

  go1();
  pii vp = go2();

  //now we are just printing out answer (for now - 1/2)
  for (int i = 1; i <= q; i++) {
    cout << ans[qus[i]] << '\n';
  }
  cout.flush();
}

//calculate the answer for one
//use a dp to calculate the answer for two (root at non-leaf)
//greedily add nodes until we get to each val (if none left - do nothing)

Compilation message

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:145:7: warning: variable 'vp' set but not used [-Wunused-but-set-variable]
   pii vp = go2();
       ^~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5120 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 5120 KB Output is correct
2 Correct 454 ms 25340 KB Output is correct
3 Correct 569 ms 33916 KB Output is correct
4 Correct 441 ms 25336 KB Output is correct
5 Correct 450 ms 26624 KB Output is correct
6 Correct 421 ms 27160 KB Output is correct
7 Correct 325 ms 27812 KB Output is correct
8 Correct 490 ms 35832 KB Output is correct
9 Correct 304 ms 30452 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 521 ms 25180 KB Output is correct
3 Correct 556 ms 39752 KB Output is correct
4 Correct 375 ms 30260 KB Output is correct
5 Correct 475 ms 33064 KB Output is correct
6 Correct 488 ms 33456 KB Output is correct
7 Correct 316 ms 36500 KB Output is correct
8 Correct 582 ms 40952 KB Output is correct
9 Correct 299 ms 36360 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5120 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 5120 KB Output is correct
2 Correct 454 ms 25340 KB Output is correct
3 Correct 569 ms 33916 KB Output is correct
4 Correct 441 ms 25336 KB Output is correct
5 Correct 450 ms 26624 KB Output is correct
6 Correct 421 ms 27160 KB Output is correct
7 Correct 325 ms 27812 KB Output is correct
8 Correct 490 ms 35832 KB Output is correct
9 Correct 304 ms 30452 KB Output is correct
10 Correct 7 ms 4992 KB Output is correct
11 Correct 521 ms 25180 KB Output is correct
12 Correct 556 ms 39752 KB Output is correct
13 Correct 375 ms 30260 KB Output is correct
14 Correct 475 ms 33064 KB Output is correct
15 Correct 488 ms 33456 KB Output is correct
16 Correct 316 ms 36500 KB Output is correct
17 Correct 582 ms 40952 KB Output is correct
18 Correct 299 ms 36360 KB Output is correct
19 Correct 8 ms 5120 KB Output is correct
20 Incorrect 456 ms 31636 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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