QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#406810#6659. 외곽 순환 도로 2Pannda0 435ms10704kbC++204.1kb2024-05-07 18:56:082024-08-26 15:52:35

Judging History

This is the latest submission verdict.

  • [2024-08-26 15:52:35]
  • 管理员手动重测本题所有提交记录
  • Verdict: 0
  • Time: 435ms
  • Memory: 10704kb
Show
  • [2024-05-07 18:56:09]
  • Judged
  • Verdict: 0
  • Time: 426ms
  • Memory: 10728kb
Show
  • [2024-05-07 18:56:08]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;

long long place_police(vector<int> par, vector<long long> wpar, vector<long long> weights) {
    par.insert(par.begin(), -1);
    wpar.insert(wpar.begin(), -1);
    int n = par.size();
    int k = weights.size();

    vector<vector<int>> adj(n);
    for (int u = 1; u < n; u++) {
        adj[par[u]].push_back(u);
    }

    int cnt = 0;
    auto dfs = [&](auto self, int u) -> vector<vector<vector<vector<long long>>>> {
        if (adj[u].empty()) {
            vector<vector<vector<vector<long long>>>> res(2, vector<vector<vector<long long>>>(2, vector<vector<long long>>(3, vector<long long>(3, INF))));
            cnt++;
            res[0][0][0][0] = 0;
            res[1][0][1][1] = 0;
            return res;
        }

        vector<vector<vector<vector<long long>>>> res(2, vector<vector<vector<long long>>>(2, vector<vector<long long>>(3, vector<long long>(3, INF))));
        for (int c = 0; c < 2; c++) {
            for (int l = 0; l < 2; l++) {
                for (int r = 0; r < 2; r++) {
                    res[c][0][l][r] = 0;
                }
            }
        }
        bool first = true;
        for (int v : adj[u]) {
            auto get = self(self, v);
            long long cost = weights[cnt - 1];
            vector<vector<vector<vector<long long>>>> upd(2, vector<vector<vector<long long>>>(2, vector<vector<long long>>(3, vector<long long>(3, INF))));
            for (int cu = 0; cu < 2; cu++) for (int tu = 0; tu < 2; tu++) {
                for (int lu = 0; lu < 3; lu++) {
                    for (int ru = 0; ru < 3; ru++) {
                        for (int cv = 0; cv < 2; cv++) for (int tv = 0; tv < 2; tv++) {
                            for (int lv = 0; lv < 3; lv++) {
                                for (int rv = 0; rv < 3; rv++) {
                                    upd[cu][tu | tv][first ? 2 : lu][2] = min(upd[cu][tu | tv][first ? 2 : lu][2], res[cu][tu][lu][ru] + get[cv][tv][lv][rv] + wpar[v]);
                                    if (cu != cv) {
                                        int t = ru <= 1 && lv <= 1 && ru == lv;
                                        upd[cu][tu | tv | t][lu][rv] = min(upd[cu][tu | tv | t][lu][rv], res[cu][tu][lu][ru] + get[cv][tv][lv][rv] + cost * t);
                                    }
                                }
                            }
                        }
                    }
                }
            }
            res = upd;
            first = false;
        }

        return res;
    };
    auto res = dfs(dfs, 0);

    long long ans = INF;

    if (k & 1) {
        for (int c = 0; c < 2; c++) {
            for (int l = 0; l < 3; l++) {
                for (int r = 0; r < 3; r++) {
                    if (l == 2 || r == 2 || l != r) {
                        ans = min(ans, res[c][1][l][r]);
                    } else {
                        ans = min(ans, res[c][0][l][r] + weights.back());
                        ans = min(ans, res[c][1][l][r] + weights.back());
                    }
                }
            }
        }
    } else {
        for (int c = 0; c < 2; c++) for (int t = 0; t < 2; t++) {
            for (int l = 0; l < 3; l++) {
                for (int r = 0; r < 3; r++) {
                    ans = min(ans, res[c][t][l][r]);
                }
            }
        }
    }

    return ans;
}

//template<class T>
//void read(vector<T> &a) {
//    if (a.empty()) {
//        T x;
//        while (cin >> x) {
//            if (x == -1) break;
//            a.push_back(x);
//        }
//    } else {
//        for (T &x : a) {
//            cin >> x;
//        }
//    }
//}
//int main() {
//    ios::sync_with_stdio(false);
//    cin.tie(nullptr);
//    int n;
//    cin >> n;
//    vector<int> par(n - 1);
//    vector<long long> wpar(n - 1);
//    vector<long long> weights;
//    for (int i = 0; i < n - 1; i++) {
//        cin >> par[i] >> wpar[i];
//    }
//    read<long long>(weights);
//    cout << place_police(par, wpar, weights);
//}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 6
Accepted
time: 0ms
memory: 3804kb

input:

5
0 452912
0 820899
0 79369
0 232463
1000000000000 1000000000000 1000000000000 1000000000000

output:

532281

result:

ok single line: '532281'

Test #2:

score: 6
Accepted
time: 0ms
memory: 3784kb

input:

6
0 581451
0 68556
0 918465
0 661406
0 41816
1000000000000 1000000000000 1000000000000 1000000000000 1000000000000

output:

1000000110372

result:

ok single line: '1000000110372'

Test #3:

score: 6
Accepted
time: 0ms
memory: 3784kb

input:

4
0 0
0 0
0 0
0 0 0

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Wrong Answer
time: 0ms
memory: 4036kb

input:

5
0 938777585449
0 576051802364
0 418735407836
0 823692221300
233950071687 338912182863 866023804654 680391493800

output:

757647590699

result:

wrong answer 1st lines differ - expected: '1333076973323', found: '757647590699'

Subtask #2:

score: 0
Wrong Answer

Test #28:

score: 0
Wrong Answer
time: 435ms
memory: 10704kb

input:

99997
0 122727
0 267270
0 846212
0 454122
0 805668
0 614161
0 7805
0 173284
0 684707
0 269129
0 930945
0 1101
0 992427
0 297412
0 759787
0 227130
0 120418
0 90914
0 333684
0 46144
0 519912
0 171490
0 823586
0 121787
0 674177
0 560254
0 753090
0 853359
0 465464
0 655527
0 631303
0 919012
0 597126
0 1...

output:

20632170738

result:

wrong answer 1st lines differ - expected: '24980330181', found: '20632170738'

Subtask #3:

score: 0
Wrong Answer

Test #36:

score: 5
Accepted
time: 0ms
memory: 3872kb

input:

11
0 9
0 8
2 0
3 7
3 1
2 6
0 0
7 7
7 1
9 6
1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000

output:

1

result:

ok single line: '1'

Test #37:

score: 0
Wrong Answer
time: 213ms
memory: 8108kb

input:

50311
0 630582
1 458618
2 300543
3 566041
4 306718
5 134260
6 736322
7 458543
8 609374
9 355623
10 706939
11 48588
12 455725
13 105118
14 71071
15 528699
16 423538
17 471781
18 98063
19 169099
20 657181
21 295537
22 49937
23 306612
24 186582
25 505763
26 831500
27 406268
28 294626
29 128111
30 42115...

output:

0

result:

wrong answer 1st lines differ - expected: '813491', found: '0'

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Wrong Answer

Test #77:

score: 0
Wrong Answer
time: 218ms
memory: 7924kb

input:

50311
0 962897543825
1 887020369743
2 363658802934
3 481009844166
4 1099712574
5 858320882162
6 521927434762
7 379344260539
8 73024776148
9 634183458545
10 869560347910
11 81581323331
12 750044298516
13 307013017409
14 306226274039
15 423923546601
16 482114694167
17 849292461119
18 299993045938
19 7...

output:

0

result:

wrong answer 1st lines differ - expected: '939418184213', found: '0'

Subtask #6:

score: 0
Skipped

Dependency #1:

0%
English 繁體中文 简体中文

Server Time: 2025-03-02 14:04:14 | OpenSource Project