QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#60670 | #2169. 'S No Problem | captured | WA | 5ms | 14776kb | C++17 | 3.3kb | 2022-11-05 23:52:18 | 2022-11-05 23:52:21 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define LL long long
#define FOR(i,n) for(int i=0;i<n;i++)
#define deb(x) cerr<<#x<<" : "<<x<<" "
#define dnl cerr<<endl
typedef pair<int,int> pii;
const int maxn = 2e5+7;
vector<pii> g[maxn];
int mark[maxn];
int D[maxn];
int parent[maxn];
int parentcost[maxn];
void dfs(int u,int p,int cost){
D[u] = cost;
parent[u] = p;
for(pii x:g[u]){
if(x.first!=p){
dfs(x.first,u,cost+x.second);
parentcost[x.first] = x.second;
}
}
}
vector<int> cnodes;
int D2[maxn];
void dfs2(int u,int p,int cost,int root){
D2[u] = cost;
cnodes.push_back(u);
for(pii x:g[u]){
if(x.first!=p){
if( !mark[x.first] or x.first==root )
dfs2(x.first,u,cost+x.second,root);
}
}
}
int maxfromdiam[maxn];
int posindiam[maxn];
int pd[maxn];
int nodeinpos[maxn];
void solve(int cs){
int n;
LL total = 0;
cin>>n;
for(int i=2;i<=n;i++){
int u,v,w;cin>>u>>v>>w;
g[u].push_back({v,w});
g[v].push_back({u,w});
total += w;
total += w;
}
dfs(1,-1,0);
int a=-1,maxi=0;
for(int i=1;i<=n;i++){
if(D[i] > maxi){
maxi = D[i];
a = i;
}
}
dfs(a,-1,0);
int b=-1;
maxi=0;
for(int i=1;i<=n;i++){
if(D[i] > maxi){
maxi = D[i];
b = i;
}
}
LL diam = maxi;
vector<int> diameter;
int z = b;
while( z != a ){
diameter.push_back(z);
z = parent[z];
}
diameter.push_back(a);
reverse(diameter.begin(),diameter.end());
int pos = 1;
for(int d:diameter){
posindiam[d] = pos;
nodeinpos[pos] = d;
pos++;
}
for(int d:diameter){
int cp = posindiam[d];
if(cp==1)pd[cp] = 0;
else{
pd[cp] = parentcost[d] + pd[cp-1];
}
}
// for(int d:diameter){
// deb(d);
// }
// dnl;
for(int d:diameter){
mark[d]=1;
}
int subdiam = 0;
for(int d:diameter){
cnodes.clear();
dfs2(d,-1,0,d);
int aa=-1,ma=-1;
for(int v:cnodes){
if(D2[v] > ma){
ma = D2[v];
aa = v;
}
}
maxfromdiam[d] = aa;
cnodes.clear();
dfs2(aa,-1,0,d);
for(int v:cnodes){
subdiam = max(subdiam,D2[v]);
}
}
LL ans = total - diam - subdiam;
LL curtot = total - diam;
set<int> cst;
maxi = 0;
for(int i=pos-1;i>1;i--){
int d = nodeinpos[i];
LL cur = maxi+maxfromdiam[ d ] + pd[i-1];
cur = total - diam - cur;
ans = max(ans,cur);
// cst.insert( maxfromdiam[d]-pd[i] );
// deb(i);deb(d);
// deb(maxfromdiam[d]);
// deb(maxi);dnl;
maxi = max(maxi,maxfromdiam[d]-pd[i]);
}
// deb(total);deb(diam);deb(subdiam);dnl;
cout<<ans<<endl;
}
/*
ATTAATTA
*/
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t=1;
// cin>>t;
for(int cs=1;cs<=t;cs++)solve(cs);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 13856kb
input:
5 1 2 1 1 3 2 1 4 3 1 5 4
output:
10
result:
ok single line: '10'
Test #2:
score: 0
Accepted
time: 3ms
memory: 14492kb
input:
6 6 2 1 4 6 1 3 1 1 1 5 1 1 6 10
output:
15
result:
ok single line: '15'
Test #3:
score: 0
Accepted
time: 5ms
memory: 14668kb
input:
6 1 3 1 3 2 1 3 4 10 5 4 1 4 6 1
output:
15
result:
ok single line: '15'
Test #4:
score: 0
Accepted
time: 2ms
memory: 14776kb
input:
6 1 3 1 2 3 1 3 5 1 4 5 1 5 6 1
output:
6
result:
ok single line: '6'
Test #5:
score: -100
Wrong Answer
time: 2ms
memory: 13596kb
input:
6 1 2 5 3 2 3 2 4 1 4 5 2 4 6 4
output:
17
result:
wrong answer 1st lines differ - expected: '16', found: '17'