Submission #107402

#	Time	Username	Problem	Language	Result	Execution time	Memory
107402		shoemakerjo	Designated Cities (JOI19_designated_cities)	C++14	7 / 100	531 ms	36016 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;

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]);
  }

  if (ops.size()) mdepth[u] = ops[0];
  if (ops.size() < 2) return;
  sort(ops.begin(), ops.end());
  reverse(ops.begin(), ops.end());
  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 (stderr)

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
• Subtask 2: 7 / 7
• Subtask 3: 0 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44