QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#386729#5102. Dungeon CrawlerckisekiWA 1ms5744kbC++203.2kb2024-04-11 19:41:072024-04-11 19:41:07

Judging History

你现在查看的是最新测评结果

  • [2024-04-11 19:41:07]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5744kb
  • [2024-04-11 19:41:07]
  • 提交

answer

#pragma GCC optimize("Ofast,no-stack-protector")
#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(auto s, auto ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int f = 0;
  (..., (cerr << (f++ ? ", " : "") << a));
  cerr << ")\e[0m\n";
}
#include <experimental/iterator>
void orange_(auto s, auto L, auto R) {
  cerr << "\e[1;33m[ " << s << " ] = [ ";
  using namespace experimental;
  copy(L, R, make_ostream_joiner(cerr, ", "));
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

constexpr int N = 2000 + 5;
constexpr int Q = 200000 + 5;

vector<pair<int, int>> g[N];

int64_t ans[Q];

vector<tuple<int, int, int>> que[Q];

int pa[N];
int64_t dep[N];
int64_t maxdep[N];
int64_t ex[N];

int tl[N], tr[N], tc;

bool anc(int u, int v) {
  return tl[u] <= tl[v] and tr[v] <= tr[u];
}

struct Bests {
  pair<int64_t, int> v[3];
  int s;
  Bests() : s{0} {}
  void add(pair<int64_t, int> x) {
    v[s++] = x;
    sort(v, v + s, greater());
    s = min(s, 2);
  }
  span<pair<int64_t, int>> vals() { return {v, v + s}; };
};

void dfs(int u, int f) {
  tl[u] = tc++;
  pa[u] = f;
  maxdep[u] = 0;
  Bests bs;
  for (auto [v, w] : g[u]) {
    if (v == f)
      continue;
    dep[v] = dep[u] + w;
    dfs(v, u);
    maxdep[u] = max(maxdep[u], maxdep[v] + w);
    bs.add({maxdep[v] + w, v});
    ex[v] = 0;
  }

  for (auto [v, w] : g[u]) {
    if (v == f)
      continue;
    for (auto [r, o] : bs.vals()) {
      if (o == v)
        continue;
      ex[v] = r + dep[u];
      break;
    }
  }

  tr[u] = tc;
}

constexpr int64_t INF = 1LL << 60;

void solve(int n, int s) {
  tc = 0;
  dep[s] = 0;
  dfs(s, s);
  for (int i = 0; i < n; ++i) {
    maxdep[i] += dep[i];
  }
  for (auto [k, t, i] : que[s]) {
    int64_t best = -INF;

    int o = t;
    while (not anc(o, k))
      o = pa[o];

    if (o == t) {
      ans[i] = -INF;
      continue;
    }

    if (not anc(t, k)) {
      int tp = t;
      while (not anc(tp, k)) {
        if (anc(pa[tp], k)) {
          best = max(best, maxdep[tp]);
          break;
        }
        tp = pa[tp];
      }
    }

    int kp = k;
    while (kp != o) {
      int64_t cur = maxdep[kp] - 2 * (dep[kp] - dep[o]);
      debug(cur);
      debug(s, kp, o, maxdep[kp], dep[kp], dep[o]);
      best = max(best, cur);
      kp = pa[kp];
    }

    while (pa[o] != s) {
      debug(o, ex[o]);
      best = max(best, ex[o]);
      o = pa[o];
    }

    ans[i] = best;
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, q;
  cin >> n >> q;
  int64_t tot = 0;
  for (int i = 1; i < n; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    --u, --v;
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
    tot += w;
  }
  for (int i = 0; i < q; ++i) {
    int s, k, t;
    cin >> s >> k >> t;
    --s, --k, --t;
    que[s].emplace_back(k, t, i);
  }
  for (int i = 0; i < n; ++i) {
    solve(n, i);
//    break;
  }
  for (int i = 0; i < q; ++i) {
    if (ans[i] == -INF) {
      cout << "impossible\n";
    } else {
      debug(ans[i]);
      cout << 2 * tot - ans[i] << '\n';
    }
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 5744kb

input:

22 5
1 2 7
2 3 5
3 4 8
3 6 6
3 7 3
2 5 6
5 8 2
8 9 11
2 10 16
1 11 12
11 12 4
11 13 9
1 14 25
14 15 4
15 16 5
15 17 6
15 18 1
15 19 8
14 20 7
20 21 9
20 22 17
1 19 9
1 9 19
1 8 9
1 9 8
2 22 11

output:

316
293
316
impossible
314

result:

wrong answer 3rd lines differ - expected: '293', found: '316'