QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#884262 | #10066. Many Pairs | guleng2007# | 0 | 1067ms | 43560kb | C++20 | 2.6kb | 2025-02-05 22:59:06 | 2025-02-05 22:59:07 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
vector <int> g[N];
int sz[N], fa[N], dep[N], son[N];
void dfs1(int x)
{
sz[x]=1;
for(auto to:g[x])
if(to!=fa[x])
{
fa[to]=x;
dep[to]=dep[x]+1;
dfs1(to);
sz[x] += sz[to];
if(sz[to]>sz[son[x]])
son[x]=to;
}
}
int top[N], dfsn[N], point[N], Indx;
void dfs2(int x,int t)
{
top[x]=t, dfsn[x]=++Indx, point[Indx]=x;
if(son[x])
dfs2(son[x],t);
for(auto to:g[x])
if(to!=fa[x] && to!=son[x])
dfs2(to,to);
}
int lca(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
swap(x,y);
x=fa[top[x]];
}
if(dep[x]<dep[y])
return x;
return y;
}
struct node
{
int x,y,c;
};
vector <node> vec[N];
int p[N], sum[N], ans[N], tot[N], out[N], alltot;
map <pair<int,int>,int> Edge;
int getfa(int x)
{
if(x!=p[x])
p[x]=getfa(p[x]);
return p[x];
}
void merge(int x,int y)
{
int fax=getfa(x), fay=getfa(y);
p[fax]=fay;
}
void dfs3(int x)
{
for(auto to:g[x])
if(to!=fa[x])
{
dfs3(to);
sum[x] += sum[to];
tot[x] += tot[to];
}
Edge.clear();
for(auto p:vec[x])
{
sum[x] += p.c;
if(p.x==x || p.y==x)
sum[getfa(p.x+p.y-x)] += p.c;
else
{
out[getfa(p.x)] += p.c;
out[getfa(p.y)] += p.c;
Edge[make_pair(min(getfa(p.x),getfa(p.y)),max(getfa(p.x),getfa(p.y)))] += p.c;
}
}
vector <int> val;
for(auto to:g[x])
if(to!=fa[x])
val.push_back(sum[to]);
sort(val.begin(),val.end(),greater<int>());
if(val.size()>=2)
ans[x]=max(ans[x],val[0]+val[1]);
else if(val.size())
ans[x]=max(ans[x],val[0]);
for(auto p:Edge)
ans[x]=max(ans[x],sum[p.first.first]+sum[p.first.second]+p.second);
vector<int> son;
for(auto to:g[x])
if(to!=fa[x])
son.push_back(to);
if(!son.size())
ans[x]=alltot;
else
{
for(auto to:son)
{
int val=alltot;
for(auto oth:son)
if(oth!=to)
val -= tot[oth];
val += sum[x]-sum[to]-out[to];
if(val<0)
assert(0);
ans[x]=max(ans[x],val);
}
}
for(auto to:g[x])
if(to!=fa[x])
merge(to,x);
}
signed main()
{
int n,k;
cin >> n >> k;
for(int i=1;i<n;i++)
{
int x,y;
scanf("%lld %lld",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
dep[1]=1;
dfs1(1);
dfs2(1,1);
for(int i=1;i<=k;i++)
{
int a,b,c;
scanf("%lld %lld %lld",&a,&b,&c);
alltot += c;
if(a==b)
assert(0);
tot[a] += c, tot[b] += c;
vec[lca(a,b)].push_back((node){a,b,c});
}
for(int i=1;i<=n;i++)
p[i]=i;
dfs3(1);
for(int i=1;i<=n;i++)
printf("%lld ",ans[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 11996kb
input:
50 50 1 20 13 1 39 1 12 1 16 1 4 1 9 1 1 17 33 1 1 28 1 46 31 1 1 23 44 1 15 1 1 7 14 1 1 40 1 25 1 34 11 1 6 1 1 30 1 3 42 1 1 48 35 1 27 1 1 45 29 1 10 1 19 1 2 1 38 1 41 1 1 37 1 32 18 1 47 1 26 1 22 1 1 5 1 50 49 1 1 21 43 1 1 8 1 36 24 1 26 20 640 41 45 742 39 15 520 20 18 703 47 16 391 2 19 97...
output:
2373 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112
result:
wrong answer 1st lines differ - expected: '1864 35112 35112 35112 35112 3...2 35112 35112 35112 35112 35112', found: '2373 35112 35112 35112 35112 3... 35112 35112 35112 35112 35112 '
Subtask #2:
score: 0
Wrong Answer
Test #9:
score: 0
Wrong Answer
time: 12ms
memory: 12792kb
input:
5000 500 1 2035 2103 1 2889 1 3899 1 1 1572 2838 1 1 3608 2582 1 1 2880 201 1 3989 1 1 1300 4071 1 2576 4504 1 3547 1 1145 3878 1 1 3240 1 2047 1 4983 3564 1 4965 4504 1 1305 3217 1 1 4820 2377 1 1640 1 1363 1 1 4731 1 4040 1 3707 3364 1 1 79 1 4968 2679 1 1 3276 1 4709 1 4438 1 3420 1 828 4504 4554...
output:
7355 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 3...
result:
wrong answer 1st lines differ - expected: '7043 332097 332097 332097 3320...097 332097 332097 332097 332097', found: '7355 332097 332097 332097 3320...97 332097 332097 332097 332097 '
Subtask #3:
score: 0
Wrong Answer
Test #15:
score: 17
Accepted
time: 14ms
memory: 14776kb
input:
5000 2000 1 2035 2103 1 2889 1 3899 1 1 1572 2838 1 1 3608 2582 1 1 2880 201 1 3989 1 1 1300 4071 1 2576 4504 1 3547 1 1145 3878 1 1 3240 1 2047 1 4983 3564 1 4965 4504 1 1305 3217 1 1 4820 2377 1 1640 1 1363 1 1 4731 1 4040 1 3707 3364 1 1 79 1 4968 2679 1 1 3276 1 4709 1 4438 1 3420 1 828 4504 455...
output:
2212740 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 13...
result:
ok single line: '2212740 130540162 130540162 13... 130540162 130540162 130540162 '
Test #16:
score: 17
Accepted
time: 4ms
memory: 12668kb
input:
5000 2000 2967 950 1 4700 3353 2511 4023 1 1300 4532 2356 3798 1300 3894 997 4696 999 3080 35 4766 3785 2028 793 2309 63 741 1766 3785 3285 586 3353 867 3730 1 2980 3727 1065 997 2678 2375 2751 1683 4691 1400 2827 2706 1548 4078 1 1376 1443 3224 2629 4159 1552 3353 4536 1300 3103 3632 3368 865 2174 ...
output:
3167789 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 12...
result:
ok single line: '3167789 129909272 129909272 12... 129909272 129909272 129909272 '
Test #17:
score: 0
Wrong Answer
time: 3ms
memory: 17008kb
input:
5000 2000 2967 3037 3043 4700 174 2511 4023 2384 1654 4532 2356 1104 386 3894 2067 4696 999 4577 35 2198 1623 2028 793 3636 63 3998 1766 2649 3285 3906 608 867 3730 247 3566 3727 1065 2247 728 2375 2649 1683 4691 4296 2827 4197 1548 2888 2904 1376 3566 3224 2629 3234 1552 3243 4536 4202 201 3632 241...
output:
129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129741991 129909272 129909272 129803447 129909272 129833295 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 ...
result:
wrong answer 1st lines differ - expected: '129909272 129909272 129909272 ...2 129909272 129909272 129909272', found: '129909272 129909272 129909272 ... 129909272 129909272 129909272 '
Subtask #4:
score: 0
Wrong Answer
Test #21:
score: 21
Accepted
time: 13ms
memory: 15072kb
input:
5000 5000 1 2035 2103 1 2889 1 3899 1 1 1572 2838 1 1 3608 2582 1 1 2880 201 1 3989 1 1 1300 4071 1 2576 4504 1 3547 1 1145 3878 1 1 3240 1 2047 1 4983 3564 1 4965 4504 1 1305 3217 1 1 4820 2377 1 1640 1 1363 1 1 4731 1 4040 1 3707 3364 1 1 79 1 4968 2679 1 1 3276 1 4709 1 4438 1 3420 1 828 4504 455...
output:
46132009 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 26490...
result:
ok single line: '46132009 2649064843 2649064843...49064843 2649064843 2649064843 '
Test #22:
score: 21
Accepted
time: 3ms
memory: 12796kb
input:
5000 5000 2967 950 1 4700 3353 2511 4023 1 1300 4532 2356 3798 1300 3894 997 4696 999 3080 35 4766 3785 2028 793 2309 63 741 1766 3785 3285 586 3353 867 3730 1 2980 3727 1065 997 2678 2375 2751 1683 4691 1400 2827 2706 1548 4078 1 1376 1443 3224 2629 4159 1552 3353 4536 1300 3103 3632 3368 865 2174 ...
output:
71850241 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 26492...
result:
ok single line: '71850241 2649293842 2649293842...49293842 2649293842 2649293842 '
Test #23:
score: 0
Wrong Answer
time: 3ms
memory: 19084kb
input:
5000 5000 2967 3037 3043 4700 174 2511 4023 2384 1654 4532 2356 1104 386 3894 2067 4696 999 4577 35 2198 1623 2028 793 3636 63 3998 1766 2649 3285 3906 608 867 3730 247 3566 3727 1065 2247 728 2375 2649 1683 4691 4296 2827 4197 1548 2888 2904 1376 3566 3224 2629 3234 1552 3243 4536 4202 201 3632 241...
output:
2649293842 2649293842 2649293842 2649293842 2646227721 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2645738482 2649293842 2649293842 2645969915 2649293842 2648356916 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 264...
result:
wrong answer 1st lines differ - expected: '2649293842 2649293842 26492938...649293842 2649293842 2649293842', found: '2649293842 2649293842 26492938...49293842 2649293842 2649293842 '
Subtask #5:
score: 0
Wrong Answer
Test #27:
score: 0
Wrong Answer
time: 1067ms
memory: 43560kb
input:
200000 200000 1861 126068 196536 190176 143836 3918 183352 173153 149804 74098 192775 110127 106287 1861 103451 149418 160851 35753 171988 21209 156996 161848 138469 165694 35753 140239 100453 199546 110790 120346 73215 149224 19332 138469 72674 21209 127832 142648 86197 174308 181332 15643 148621 1...
output:
1640901879 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105...
result:
wrong answer 1st lines differ - expected: '1640901879 105069892770 105069...92770 105069892770 105069892770', found: '1640901879 105069892770 105069...2770 105069892770 105069892770 '