QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#406771 | #6659. 외곽 순환 도로 2 | Pannda | 0 | 135ms | 10628kb | C++20 | 3.3kb | 2024-05-07 18:05:08 | 2024-05-07 18:05:10 |
Judging History
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%