QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#406771#6659. 외곽 순환 도로 2Pannda0 135ms10628kbC++203.3kb2024-05-07 18:05:082024-05-07 18:05:10

Judging History

你现在查看的是测评时间为 2024-05-07 18:05:10 的历史记录

  • [2024-08-26 15:52:33]
  • 管理员手动重测本题所有提交记录
  • 测评结果:0
  • 用时:138ms
  • 内存:10672kb
  • [2024-05-07 18:05:10]
  • 评测
  • 测评结果:0
  • 用时:135ms
  • 内存:10628kb
  • [2024-05-07 18:05:08]
  • 提交

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<long long>>> {
        if (adj[u].empty()) {
            vector<vector<vector<long long>>> res(2, vector<vector<long long>>(3, vector<long long>(3, INF)));
            cnt++;
            res[0][0][0] = 0;
            res[1][1][1] = 0;
            return res;
        }

        vector<vector<vector<long long>>> res(2, vector<vector<long long>>(3, vector<long long>(3, 0)));
        bool first = true;
        for (int v : adj[u]) {
            auto get = self(self, v);
            long long cost = weights[cnt - 1];
            vector<vector<vector<long long>>> upd(2, vector<vector<long long>>(3, vector<long long>(3, INF)));
            for (int cu = 0; cu < 2; cu++) {
                for (int lu = 0; lu < 3; lu++) {
                    for (int ru = 0; ru < 3; ru++) {
                        for (int cv = 0; cv < 2; cv++) {
                            for (int lv = 0; lv < 3; lv++) {
                                for (int rv = 0; rv < 3; rv++) {
                                    upd[cu][first ? 2 : lu][2] = min(upd[cu][lu][2], res[cu][lu][ru] + get[cv][lv][rv] + wpar[v]);
                                    if (cu != cv) {
                                        upd[cu][lu][rv] = min(upd[cu][lu][rv], res[cu][lu][ru] + get[cv][lv][rv] + cost * (ru <= 1 && lv <= 1 && ru == lv));
                                    }
                                }
                            }
                        }
                    }
                }
            }
            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][l][r]);
                    }
                }
            }
        }
    } else {
        for (int c = 0; c < 2; c++) {
            for (int l = 0; l < 3; l++) {
                for (int r = 0; r < 3; r++) {
                    ans = min(ans, res[c][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;
//    read<int>(par);
//    read<long long>(wpar);
//    read<long long>(weights);
//    cout << place_police(par, wpar, weights);
//}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 6
Accepted
time: 1ms
memory: 3780kb

input:

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

output:

532281

result:

ok single line: '532281'

Test #2:

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

input:

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

output:

729962

result:

wrong answer 1st lines differ - expected: '1000000110372', found: '729962'

Subtask #2:

score: 0
Wrong Answer

Test #28:

score: 0
Wrong Answer
time: 135ms
memory: 10628kb

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: 1ms
memory: 4028kb

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: 54ms
memory: 7592kb

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: 63ms
memory: 7792kb

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%