QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #874504 | #9687. 仙人掌染色 | JohnAlfnov# | 0 | 45ms | 14668kb | C++14 | 994b | 2025-01-28 09:29:53 | 2025-01-28 09:29:55 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,m,p;
vector<pair<int,int>>g[200005];
long long f0[200005],f1[200005];
void dfs0(int x,int la,int c2){
int d=0;
long long ff=0;
vector<long long>vc;
for(auto pi:g[x]){
++d;int cu=pi.first,cc=pi.second;
if(cu==la)continue;
dfs0(cu,x,cc);ff+=f0[cu];
vc.emplace_back(f1[cu]-f0[cu]);
}
sort(vc.begin(),vc.end(),greater<int>());
f0[x]=ff;f1[x]=1ll*d*(d-1)*p-c2;
int sz=vc.size();
__int128 he=0;
for(int i=0;i<sz;++i){
he+=vc[i];
f0[x]=max((__int128)f0[x],he+1ll*(i+1)*(d-i-1)*d*p+ff);
if(la)f1[x]=max((__int128)f1[x],he-c2+1ll*(i+2)*(d-i-2)*d*p+ff);
}
}
int main(){
scanf("%d%d%d",&n,&m,&p);
for(int i=1;i<=m;++i){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);w*=2;
g[u].emplace_back(v,w);
g[v].emplace_back(u,w);
}
if(m==n-1){
dfs0(1,0,0);long long an=f0[1];
for(int i=2;i<=n;++i){
dfs0(i,0,0);assert(f0[i]==an);
}
printf("%lld\n",an/2);
return 0;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
input:
20 19 444 1 2 932 2 3 9129 1 4 3180 4 5 502 4 6 3906 4 7 4020 4 8 2771 2 9 4132 6 10 3311 2 11 1547 3 12 7576 11 13 1254 6 14 1653 7 15 6855 6 16 8691 5 17 2048 3 18 8097 12 19 2113 10 20 2594 0 0 1 0 2 0 1 1 2 3 2 4 2 5 2 6 2 1 3 4 2 2 3 0 3 2 3 5 3 7 3 6 3 3 3 1 4 0 4 1
output:
result:
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #2:
0%
Subtask #6:
score: 0
Skipped
Dependency #4:
0%
Subtask #7:
score: 0
Wrong Answer
Test #35:
score: 0
Wrong Answer
time: 40ms
memory: 14468kb
input:
175359 200000 988 88931 90388 0 153878 127005 0 51428 146698 0 47233 44294 0 165647 94047 0 166749 168430 0 72728 87056 0 166749 113491 0 53604 116732 0 124969 120242 0 149669 118248 0 132892 45646 0 159774 167127 0 166749 148203 0 166749 129635 0 144811 121866 0 79510 144556 0 12541 75600 0 166749 ...
output:
result:
wrong output format Unexpected end of file - token expected
Subtask #8:
score: 0
Wrong Answer
Test #36:
score: 0
Wrong Answer
time: 45ms
memory: 14668kb
input:
169178 200000 1 108026 106006 1 130712 146166 1 103490 133909 1 168608 113741 1 113670 115210 1 41692 127482 1 88594 91086 1 73606 78011 1 47848 99392 1 138615 97485 1 133884 131888 1 126125 47540 1 42576 147882 1 105365 109903 1 71043 153403 1 104808 113745 1 63589 160217 1 52766 161917 1 112636 13...
output:
result:
wrong output format Unexpected end of file - token expected
Subtask #9:
score: 0
Skipped
Dependency #5:
0%