Submission #107411

#	Time	Username	Problem	Language	Result	Execution time	Memory
107411		shoemakerjo	Designated Cities (JOI19_designated_cities)	C++14	100 / 100	952 ms	62480 KiB

designated_cities

#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;

//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];
ll pplink[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;
    plink[u] = 0LL;
  }
  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;
    pplink[vp.first] = vp.second.first;
    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 st[maxn];
int en[maxn];
vector<int> stuff;

void etour(int u) {
  st[u] = stuff.size();
  stuff.push_back(u);
  for (pil vp : adj[u]) {
    if (vp.first != par[u]) {
      etour(vp.first);
    }
  }
  en[u] = stuff.size()-1;
}

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

void delaze(int ss, int se, int si) {
  seg[si] = mp(seg[si].first + lazy[si], seg[si].second);
  if (lazy[si] && ss != se) {
    lazy[si*2+1] += lazy[si];
    lazy[si*2+2] += lazy[si];
  }
  lazy[si] = 0;
}

pli query() {
  //get the maximum
  delaze(0, n-1, 0);
  return seg[0];
}

void upd(int us, int ue, ll diff, int ss = 0, int se = n-1,
    int si = 0) {
  delaze(ss, se, si);
  if (us > ue || ss > se || us > se || ue < ss) return;
  if (us <= ss && se <= ue) {
    lazy[si] += diff;
    delaze(ss, se, si);
    return;
  }
  int mid = (ss+se)/2;
  upd(us, ue, diff, ss, mid, si*2+1);
  upd(us, ue, diff, mid+1, se, si*2+2);
  seg[si] = max(seg[si*2+1], seg[si*2+2]);
}

bool isrem[maxn];

void buildtree(int ss = 0, int se  = n-1, int si = 0) {
  if (ss == se) {
    seg[si] = {dep[stuff[ss]], stuff[ss]};
    return;
  }
  int mid = (ss+se)/2;
  buildtree(ss, mid, si*2+1);
  buildtree(mid+1, se, si*2+2);
  seg[si] = max(seg[si*2+1], seg[si*2+2]);
}

void proc(int u) {
  //remove this node
  //go up the parents list
  //all children of me lose going up (keep doing this)
  while (!isrem[u]) {
    // cout << " ----- " << u << endl;
    isrem[u] = true;
    upd(st[u], en[u], 0-pplink[u]);
    u = par[u];
  }
}

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) << endl;
      }
    }
    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();

  // cout << "got 2 : " << vp.first << " " << vp.second << endl;
  //we get the two guys
  rt = par[vp.first];
  dfs(rt); //reset everything (yea)
  etour(rt);
  // cout << "done the dfs" << endl;

  ll cans = ans[2]; //starting answer (will increase)
  //now we do the greedy thing
  buildtree(); //just start all as it is

  // cout << "built the tree" << endl;

  isrem[rt] = true; //basically is removed
  proc(vp.first);
  proc(vp.second);

  for (int i = 3; i <= n; i++) {
    pli tmp = query();
    if (tmp.first != 0) {
      cans -= tmp.first;
      proc(tmp.second);
      // cout << "removing " << tmp.second << " "
      //   << tmp.first << endl;
    }
    else {
      assert(cans == 0LL);
    }
    ans[i] = cans;
  }

  //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)

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 17 / 17
• Subtask 5: 17 / 17
• Subtask 6: 44 / 44