QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#60670#2169. 'S No ProblemcapturedWA 5ms14776kbC++173.3kb2022-11-05 23:52:182022-11-05 23:52:21

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-05 23:52:21]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:14776kb
  • [2022-11-05 23:52:18]
  • 提交

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'