Submission #1162090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162090		fryingduc	Designated Cities (JOI19_designated_cities)	C++20	9 / 100	134 ms	29184 KiB

designated_cities

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 2e5 + 5;
int n, q;
vector<pair<int, int>> g[maxn];
int eu[maxn], ev[maxn], ec[maxn], ed[maxn];
int par[maxn];
long long tot;
long long res[maxn];
long long dep[maxn];

void pre_dfs(int u, int prev) {
  for (auto [v, id] : g[u]) {
    if (v == prev) continue;
    par[v] = u;
    dep[v] = dep[u] + (v == ev[id] ? ec[id] : ed[id]);
    pre_dfs(v, u);
  }
}

void solve() {
  cin >> n;
  for (int i = 1; i < n; ++i) {
    int u, v; cin >> u >> v >> ec[i] >> ed[i];
    g[u].emplace_back(v, i);
    g[v].emplace_back(u, i);
    eu[i] = u, ev[i] = v;
  }
  pre_dfs(1, 0);
  int r1 = max_element(dep + 1, dep + n + 1) - dep;
  dep[r1] = par[r1] = 0;
  pre_dfs(r1, 0);
  int r2 = 0;
  for (int i = 1; i <= n; ++i) {
    if (i == r1) continue;
    if (r2 == 0 || dep[r2] < dep[i]) r2 = i;
  }
  long long tot = 0;
  for (int i = 1; i < n; ++i) {
    tot += (par[ev[i]] == eu[i] ? ec[i] : ed[i]);
  }
  cin >> q;
  if (q == 1) {
    int x; cin >> x;
    if (x == 2) {
      cout << tot - dep[r2];
    }
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

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