QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#386748#5102. Dungeon CrawlerckisekiWA 1ms5840kbC++203.2kb2024-04-11 19:49:522024-04-11 19:49:52

Judging History

This is the latest submission verdict.

  • [2024-04-11 19:49:52]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 5840kb
  • [2024-04-11 19:49:52]
  • Submitted

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 (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: 100
Accepted
time: 1ms
memory: 5748kb

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
293
impossible
314

result:

ok 5 lines

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 5840kb

input:

100 100
1 2 289384
2 3 930887
2 4 692778
4 5 636916
4 6 747794
4 7 238336
4 8 885387
8 9 760493
8 10 516650
8 11 641422
8 12 202363
8 13 490028
8 14 368691
8 15 520060
8 16 897764
16 17 513927
16 18 180541
16 19 383427
16 20 89173
16 21 455737
16 22 5212
16 23 595369
16 24 702568
16 25 956430
16 26 ...

output:

103526917
103484292
105633958
107777494
104883458
104775512
105434682
107735332
108065173
105371370
104677980
104175650
105887913
105925110
103971939
105376499
105223283
104153426
105082245
105413188
108192116
104800548
104952840
104138329
107167151
104428894
106985688
104385328
104530012
105460460
...

result:

wrong answer 3rd lines differ - expected: '106288816', found: '105633958'