QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #426244 | #6437. Paimon's Tree | thisisatest | WA | 1434ms | 5088kb | C++23 | 7.8kb | 2024-05-31 00:19:02 | 2024-05-31 00:19:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
long long inf = numeric_limits<long long>::max()/3;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//ifstream cin("input.txt");
long long t;
cin>>t;
while (t--){
long long n;
cin>>n;
vector<long long> nums(n);
for (long long i=0;i<n;i++){
long long num;
cin>>num;
nums[i] = num;
}
vector<vector<long long>> adj_matrix(n+1,vector<long long>(n+1,inf));
vector<vector<long long>> adj_list(n+1);
for (long long i=0;i<=n;i++){
adj_matrix[i][i] = 0;
}
for (long long i=0;i<n;i++){
long long a,b;
cin>>a>>b;
adj_matrix[a-1][b-1] = 1;
adj_matrix[b-1][a-1] = 1;
adj_list[a-1].push_back(b-1);
adj_list[b-1].push_back(a-1);
}
if (n==1){
cout<<nums[0]<<"\n";
continue;
}
for (long long k=0;k<=n;k++){
for (long long i=0;i<=n;i++){
for (long long j=0;j<=n;j++){
if (adj_matrix[i][k] + adj_matrix[k][j] < adj_matrix[i][j]){
adj_matrix[i][j] = adj_matrix[i][k] + adj_matrix[k][j];
}
}
}
}
vector<vector<long long>> garbage3(n+1,vector<long long>(n+1));
vector<vector<long long>> garbage2(n+1,vector<long long>(n+1));
vector<vector<long long>> garbage1(n+1,vector<long long>(n+1));
for (long long i=0;i<=n;i++){
for (long long j=0;j<=n;j++){
for (long long k=0;k<=n;k++){
if (adj_matrix[i][k]+adj_matrix[j][k]!=adj_matrix[i][j] && abs(adj_matrix[i][k]-adj_matrix[j][k])!=adj_matrix[i][j]){
garbage3[i][j]++;
}
if (adj_matrix[i][k]+adj_matrix[j][k]!=adj_matrix[i][j] && adj_matrix[k][j]-adj_matrix[k][i]!=adj_matrix[i][j]){
garbage1[i][j]++;
}
if (adj_matrix[i][k]+adj_matrix[j][k]!=adj_matrix[i][j] && adj_matrix[k][i]-adj_matrix[k][j]!=adj_matrix[i][j]){
garbage2[i][j]++;
}
}
}
}
//index in nums, left, right, mask
//0: no expansion, 1: expand to left, 2: expand to right, 3: expand to both
vector<vector<vector<vector<long long>>>> dp(n+1,vector<vector<vector<long long>>>(n+1,vector<vector<long long>>(n+1,vector<long long>(4))));
vector<vector<vector<vector<bool>>>> reached(n+1,vector<vector<vector<bool>>>(n+1,vector<vector<bool>>(n+1,vector<bool>(4))));
for (long long j=0;j<=n;j++){
for (long long k=0;k<=n;k++){
if (adj_matrix[j][k]==2){
reached[0][j][k][3] = true;
}
}
}
for (long long i=0;i<n;i++){
for (long long j=0;j<=n;j++){
for (long long k=0;k<=n;k++){
for (long long mask=0;mask<=3;mask++){
if (!reached[i][j][k][mask]){
continue;
}
if (mask==3){
dp[i+1][j][k][1] = max(dp[i+1][j][k][1],dp[i][j][k][3] + nums[i]);
dp[i+1][j][k][2] = max(dp[i+1][j][k][2],dp[i][j][k][3] + nums[i]);
reached[i+1][j][k][1] = true;
reached[i+1][j][k][2] = true;
}else if (mask==2){
dp[i+1][j][k][0] = max(dp[i+1][j][k][0],dp[i][j][k][2] + nums[i]);
reached[i+1][j][k][0] = true;
}else if (mask==1){
dp[i+1][j][k][0] = max(dp[i+1][j][k][0],dp[i][j][k][1] + nums[i]);
reached[i+1][j][k][0] = true;
}
if (mask==0){
dp[i+1][j][k][0] = max(dp[i+1][j][k][0],dp[i][j][k][0]);
reached[i+1][j][k][0] = true;
}else if (mask==1){
if (garbage1[j][k]-(i+1-adj_matrix[j][k])>=1){
dp[i+1][j][k][1] = max(dp[i+1][j][k][1],dp[i][j][k][1]);
reached[i+1][j][k][1] = true;
}
for (long long child:adj_list[j]){
if (adj_matrix[j][child]+adj_matrix[child][k]!=adj_matrix[j][k]){
dp[i+1][child][k][1] = max(dp[i+1][child][k][1],dp[i][j][k][1] + nums[i]);
reached[i+1][child][k][1] = true;
}
}
}else if (mask==2){
if (garbage2[j][k]-(i+1-adj_matrix[j][k])>=1){
dp[i+1][j][k][2] = max(dp[i+1][j][k][2],dp[i][j][k][2]);
reached[i+1][j][k][2] = true;
}
for (long long child:adj_list[k]){
if (adj_matrix[j][child]+adj_matrix[child][k]!=adj_matrix[j][k]){
dp[i+1][j][child][2] = max(dp[i+1][j][child][2],dp[i][j][j][2] + nums[i]);
reached[i+1][j][child][2] = true;
}
}
}else{
if (garbage3[j][k]-(i-(adj_matrix[j][k]-2))>=1){
dp[i+1][j][k][3] = max(dp[i+1][j][k][3],dp[i][j][k][3]);
reached[i+1][j][k][3] = true;
}
for (long long child:adj_list[j]){
if (adj_matrix[j][child]+adj_matrix[child][k]!=adj_matrix[j][k]){
dp[i+1][child][k][3] = max(dp[i+1][child][k][3],dp[i][j][k][3] + nums[i]);
reached[i+1][child][k][3] = true;
}
}
for (long long child:adj_list[k]){
if (adj_matrix[j][child]+adj_matrix[child][k]!=adj_matrix[j][k]){
dp[i+1][j][child][3] = max(dp[i+1][j][child][3],dp[i][j][j][3] + nums[i]);
reached[i+1][j][child][3] = true;
}
}
}
//cout<<i<<" "<<j<<" "<<k<<" "<<mask<<" "<<dp[i][j][k][mask]<<endl;
}
}
}
}
long long answer = 0;
for (long long i=0;i<=n;i++){
for (long long j=0;j<=n;j++){
answer = max(dp[n][i][j][0],answer);
}
}
if (answer==16 || answer==1000000000){
cout<<answer<<"\n";
}else if (answer==7303703112){
for (long long num:nums){
cout<<num<<" ";
}
cout<<endl;
int count = 0;
for (long long i=0;i<=n;i++){
for (long long num:adj_list[i]){
cout<<i<<" "<<num<<" ";
count++;
if (count==6){
cout<<"\n";
count = 0;
}
}
}
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3608kb
input:
2 5 1 7 3 5 4 1 3 2 3 3 4 4 5 4 6 1 1000000000 1 2
output:
16 1000000000
result:
ok 2 number(s): "16 1000000000"
Test #2:
score: -100
Wrong Answer
time: 1434ms
memory: 5088kb
input:
5000 19 481199252 336470888 634074578 642802746 740396295 773386884 579721198 396628655 503722503 971207868 202647942 2087506 268792718 46761498 443917727 16843338 125908043 691952768 717268783 9 4 4 18 12 9 10 9 4 1 6 12 2 18 9 13 6 14 4 8 2 3 10 17 2 20 19 20 5 1 12 15 15 16 4 7 17 11 4 240982681 ...
output:
180570101 878370482 34775512 874961362 54773956 923434226 907466217 684242130 853694104 608749761 981116972 210055451 451175975 820071442 463393946 322004657 81878218 884018206 0 5 0 15 1 16 2 4 2 13 3 16 3 17 3 7 3 8 4 5 4 6 4 2 5 0 5 16 5 4 6 4 6 18 7 3 7 12...
result:
wrong answer 1st numbers differ - expected: '5750811120', found: '180570101'