QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#91196#5102. Dungeon Crawler_skb_TL 2ms3440kbC++116.1kb2023-03-27 17:16:422023-03-27 17:16:46

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-27 17:16:46]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:3440kb
  • [2023-03-27 17:16:42]
  • 提交

answer

// Not my code. Source : https://github.com/SnapDragon64/ACMFinalsSolutions/blob/master/finals2021/dungeoncrawlerDK.cc


#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  int N, Q, U, V, W, S, K, T;
  while (cin >> N >> Q) {
    vector<vector<pair<int,int>>> c(N);
    int64_t tot = 0;
    for (int i = 0; i < N-1; i++) {
      cin >> U >> V >> W;
      U--; V--;
      c[U].push_back({V, W});
      c[V].push_back({U, W});
      tot += W;
    }

    vector<int> depth(N);
    vector<vector<pair<int64_t,int>>> longest(N);
    function<int64_t(int,int,int)> doLongest = [&](int x, int prev, int dp) {
      depth[x] = dp;
      int64_t ret = 0;
      for (auto [y, d] : c[x]) {
        longest[x].push_back({y == prev ? -1 : d+doLongest(y, x, dp+1), y});
        ret = max(ret, longest[x].back().first);
      }
      return ret;
    };
    doLongest(0, -1, 0);
    function<int64_t(int,int,int)> getLongest = [&](int x, int ex1, int ex2) -> int64_t {
      for (auto [l, y] : longest[x]) {
        if (y != ex1 && y != ex2) return l;
      }
      return 0;
    };
    function<void(int,int,int64_t)> doParLongest = [&](int x, int prev, int64_t parLongest) {
      for (auto& [l, _] : longest[x]) if (l == -1) l = parLongest;
      sort(longest[x].begin(), longest[x].end(), greater<pair<int64_t,int>>());
      for (auto [y, d] : c[x]) if (y != prev) doParLongest(y, x, d + getLongest(x, y, -1));
    };
    doParLongest(0, -1, 0);

    vector<vector<int>> skipNd(N);  // skip-paths going up the tree of length 2^n
    vector<vector<int>> skipPrev(N);  // first node on the skip-path going down
    vector<vector<int64_t>> skipSUp(N);  // max path-to-endpoint, starting at bottom, maybe entering interior subtree
    vector<vector<int64_t>> skipSDn(N);  // same, but starting at top instead
    vector<vector<int64_t>> skipKUp(N);  // skipSUp, but costs along the skip path are subtracted, not added
    vector<vector<int64_t>> skipKDn(N);  // same, but starting at top instead
    vector<vector<int64_t>> skipDist(N);  // total length of skip
    function<void(int,int,int64_t)> doSkip = [&](int x, int prev, int64_t d) {
      skipNd[x].push_back(prev);
      skipPrev[x].push_back(x);
      skipDist[x].push_back(d);
      skipSUp[x].push_back(d);
      skipSDn[x].push_back(d);
      skipKUp[x].push_back(0);
      skipKDn[x].push_back(0);
      for (int b = 1; (depth[x]&((1<<b)-1)) == 0; b++) {
        int y = skipNd[x][b-1];
        skipNd[x].push_back(skipNd[y][b-1]);
        skipPrev[x].push_back(skipPrev[y][b-1]);
        skipDist[x].push_back(skipDist[x][b-1] + skipDist[y][b-1]);
        int64_t ymx = getLongest(y, skipPrev[x][b-1], skipNd[y][0]);
        skipSUp[x].push_back(max(skipSUp[x][b-1],  skipDist[x][b-1] + max(ymx, skipSUp[y][b-1])));
        skipSDn[x].push_back(max(skipSDn[y][b-1],  skipDist[y][b-1] + max(ymx, skipSDn[x][b-1])));
        skipKUp[x].push_back(max(skipKUp[x][b-1], -skipDist[x][b-1] + max(ymx, skipKUp[y][b-1])));
        skipKDn[x].push_back(max(skipKDn[y][b-1], -skipDist[y][b-1] + max(ymx, skipKDn[x][b-1])));
      }
      for (int i = 0; i < c[x].size(); i++) if (c[x][i].first != prev) doSkip(c[x][i].first, x, c[x][i].second);
    };
    for (int i = 0; i < c[0].size(); i++) doSkip(c[0][i].first, 0, c[0][i].second);

    auto anc = [&](int x, int y) {
      vector<pair<int,int>> ret;
      while (depth[y] > depth[x]) {
        for (int b = skipNd[y].size()-1; b >= 0; b--) if (depth[y]-(1<<b) >= depth[x]) {
          y = skipNd[y][b];
          break;
        }
      }
      while (depth[x] > depth[y]) {
        for (int b = skipNd[x].size()-1; b >= 0; b--) if (depth[x]-(1<<b) >= depth[y]) {
          ret.push_back({x, b});
          x = skipNd[x][b];
          break;
        }
      }
      while (x != y) {
        for (int b = skipNd[x].size()-1; b >= 0; b--) if (b == 0 || skipNd[x][b] != skipNd[y][b]) {
          ret.push_back({x, b});
          x = skipNd[x][b]; y = skipNd[y][b];
          break;
        }
      }
      ret.push_back({x, -1});
      return ret;
    };

    for (int q = 0; q < Q; q++) {
      cin >> S >> K >> T;
      S--; K--; T--;

      auto sk = anc(S, K), st = anc(S, T), ks = anc(K, S), kt = anc(K, T);
      auto path1 = (depth[sk.back().first] > depth[st.back().first] ? sk : st);
      auto path2 = anc(path1.back().first, K);
      auto path4 = (depth[ks.back().first] > depth[kt.back().first] ? ks : kt);
      auto path3 = anc(path4.back().first, S);
      if (path1.back().first == T || path4.back().first == T) { cout << "impossible" << endl; continue; }

      int x = S, prev = -1;
      int64_t base = 0, ret = 0;
      for (int i = 0; i+1 < path1.size(); i++) {  // path1 rises from S, not overlapping path T->K
        auto [y, b] = path1[i];
        ret = max(ret, base + getLongest(x, prev, skipNd[y][0]));
        ret = max(ret, base + skipSUp[y][b]);
        base += skipDist[y][b];
        prev = skipPrev[y][b];
        x = skipNd[y][b];
      }
      for (int i = 0; i+1 < path2.size(); i++) {  // path2 rises from path1, overlapping path T->K
        auto [y, b] = path2[i];
        ret = max(ret, base + getLongest(x, prev, skipNd[y][0]));
        ret = max(ret, base + skipKUp[y][b]);
        base -= skipDist[y][b];
        prev = skipPrev[y][b];
        x = skipNd[y][b];
      }
      for (int i = path3.size()-2; i >= 0; i--) {  // path3 descends from path2, not overlapping path T->K
        auto [y, b] = path3[i];
        ret = max(ret, base + getLongest(x, prev, skipPrev[y][b]));
        ret = max(ret, base + skipSDn[y][b]);
        base += skipDist[y][b];
        prev = skipNd[y][0];
        x = y;
      }
      for (int i = path4.size()-2; i >= 0; i--) {  // path4 descends from path3, overlapping path T->K
        auto [y, b] = path4[i];
        ret = max(ret, base + getLongest(x, prev, skipPrev[y][b]));
        ret = max(ret, base + skipKDn[y][b]);
        base -= skipDist[y][b];
        prev = skipNd[y][0];
        x = y;
      }
      ret = max(ret, base + getLongest(x, prev, -1));
      cout << 2*tot - ret << endl;
    }
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3392kb

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: 0
Accepted
time: 1ms
memory: 3428kb

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
106288816
104379596
104405611
104775512
105434682
105291604
103838430
105371370
104677980
104175650
105894571
104509242
103971939
105376499
105223283
104153426
105082245
105413188
104130613
104800548
106846555
104138329
103769253
105456754
104044745
104385328
106973740
105460460
...

result:

ok 100 lines

Test #3:

score: 0
Accepted
time: 2ms
memory: 3412kb

input:

10 6
1 2 4
2 3 7
2 4 8
4 5 6
4 6 4
4 7 6
4 8 7
8 9 3
8 10 10
3 8 1
10 4 7
1 7 3
7 2 9
8 10 3
4 1 6

output:

99
78
97
87
88
93

result:

ok 6 lines

Test #4:

score: 0
Accepted
time: 0ms
memory: 3400kb

input:

10 9
9 2 5
9 1 6
9 4 97
9 7 2
9 8 42
9 10 11
9 6 77
9 3 14
9 5 9
4 7 10
7 3 8
8 7 9
1 4 8
10 7 4
7 1 2
10 1 5
10 7 2
8 4 10

output:

352
427
impossible
443
418
427
418
418
407

result:

ok 9 lines

Test #5:

score: 0
Accepted
time: 2ms
memory: 3384kb

input:

9 9
2 3 48
9 5 31
7 3 97
4 3 16
1 7 24
5 3 82
8 2 51
6 4 33
1 2 8
3 6 8
1 6 3
9 5 6
2 6 4
5 6 1
9 6 4
2 8 9
4 9 2

output:

530
643
impossible
530
impossible
561
impossible
595
627

result:

ok 9 lines

Test #6:

score: 0
Accepted
time: 0ms
memory: 3424kb

input:

8 9
1 7 51
7 6 86
2 3 62
8 4 72
5 6 17
4 1 75
3 1 41
2 3 7
5 8 4
6 1 3
8 6 2
4 2 7
8 5 6
2 1 5
7 1 6
6 7 8

output:

551
impossible
524
558
579
impossible
551
705
524

result:

ok 9 lines

Test #7:

score: 0
Accepted
time: 2ms
memory: 3416kb

input:

9 9
5 4 13
9 2 10
1 9 25
7 6 34
4 2 77
3 8 67
8 1 57
6 9 100
6 4 1
4 1 7
3 2 9
4 9 7
7 9 3
6 2 1
2 8 4
8 6 2
6 5 9

output:

517
545
impossible
530
483
517
642
584
impossible

result:

ok 9 lines

Test #8:

score: 0
Accepted
time: 0ms
memory: 3440kb

input:

10 10
2 4 26
9 8 39
4 5 88
6 3 70
7 6 7
10 4 41
8 3 57
1 6 15
5 6 9
2 8 6
3 9 1
5 7 8
4 7 8
7 6 4
2 7 3
6 8 2
5 4 10
4 8 9
1 5 9

output:

impossible
496
529
441
531
415
566
529
441
523

result:

ok 10 lines

Test #9:

score: 0
Accepted
time: 2ms
memory: 3340kb

input:

10 9
3 2 6
2 1 18
8 1 44
1 9 42
6 3 72
10 8 46
7 10 93
5 3 11
4 10 13
7 3 1
8 2 5
7 5 4
5 10 8
3 1 4
6 4 3
10 1 6
5 10 8
2 10 4

output:

impossible
550
584
impossible
483
impossible
504
impossible
489

result:

ok 9 lines

Test #10:

score: -100
Time Limit Exceeded

input:

2000 199998
126 244 481188299
718 1159 740107180
1327 1250 248943862
977 1092 780169400
826 27 932696654
1668 638 478193038
229 174 176675890
1251 646 843918836
102 1973 593920932
236 218 165399894
760 151 890198591
232 502 10739184
1961 1409 45917915
548 1840 974742709
1096 630 280975617
1110 1048 ...

output:

1266421864327
impossible
1003453161105
1017793822920
1056758437569
impossible
1249128162612
1233756636475
1354563020262
1275484665657
impossible
impossible
1644448395794
impossible
impossible
impossible
1305598243001
1730425595360
1090858373772
1180211385304
1235543994987
1894692656465
impossible
12...

result: