Submission #1051041

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051041		Ahmed57	Hard route (IZhO17_road)	C++17	100 / 100	474 ms	151696 KiB

road

#include "bits/stdc++.h"

using namespace std;
#define int long long
vector<int> adj[500001];
int mx[500001];
int cnt[500001];
pair<int,int> pref[500001];
long long overMA = 0;
long long overCNT = 1;
void dfs(int i,int pr){
    mx[i] = 0 , cnt[i] = 1;
    for(auto j:adj[i]){
        if(j==pr)continue;
        dfs(j,i);
        if(mx[j]+1>mx[i]){
            mx[i] = mx[j]+1;
            cnt[i] = 0;
        }
        if(mx[j]+1==mx[i]){
            cnt[i]+=cnt[j];
        }
    }
}
void reroot(int i,int pr,int MA,int CNT){
    vector<pair<int,int>> v;
    if(MA)v.push_back({MA,CNT});
    for(auto j:adj[i]){
        if(j==pr)continue;
        v.push_back({mx[j]+1,cnt[j]});
    }
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    if(v.size()>=3){
        int z = v[0].first , y = v[1].first , x = v[2].first;
        long long cost = 0;
        if(x<y&&y<z){
            int A = v[0].second , B = v[1].second , C = v[2].second;
            for(int i = 3;i<v.size();i++)if(v[i].first==x)C+=v[i].second;
            cost = B*C;
        }else if(x<y&&y==z){
            int A = v[0].second , B = v[1].second , C = v[2].second;
            for(int i = 3;i<v.size();i++)if(v[i].first==x)C+=v[i].second;
            cost = (A+B)*C;
        }else if(x==y&&y<z){
            int A = v[0].second , B = v[1].second , C = v[2].second;
            cost = B*C;
            long long sum = B+C;
            for(int i = 3;i<v.size();i++){
                if(v[i].first==x){
                    cost+=sum*v[i].second;
                    sum+=v[i].second;
                }
            }
        }else if(x==y&&y==z){
            int A = v[0].second , B = v[1].second , C = v[2].second;
            cost = A*B+(A+B)*C;
            long long sum = A+B+C;
            for(int i = 3;i<v.size();i++){
                if(v[i].first==x){
                    cost+=sum*v[i].second;
                    sum+=v[i].second;
                }
            }
        }
        if(overMA<(x+y)*z){
            overMA = (x+y)*z;
            overCNT = 0;
        }
        if(overMA==(x+y)*z){
            overCNT+=cost;
        }
    }
    pair<int,int> cur = {MA,CNT};
    for(auto j:adj[i]){
        if(j==pr)continue;
        pref[j] = cur;
        if(mx[j]+1>cur.first){
            cur.first = mx[j]+1;
            cur.second = 0;
        }
        if(mx[j]+1==cur.first){
            cur.second+=cnt[j];
        }
    }
    reverse(adj[i].begin(),adj[i].end());
    cur = {-1e9,0};
    for(auto j:adj[i]){
        if(j==pr)continue;
        if(cur.first>pref[j].first)pref[j] = cur;
        else if(cur.first==pref[j].first)pref[j].second+=cur.second;
        if(mx[j]+1>cur.first){
            cur.first = mx[j]+1;
            cur.second = 0;
        }
        if(mx[j]+1==cur.first){
            cur.second+=cnt[j];
        }
    }
    reverse(adj[i].begin(),adj[i].end());
    for(auto j:adj[i]){
        if(j==pr)continue;
        reroot(j,i,pref[j].first+1,pref[j].second);
    }
}
signed main(){
    int n;
    cin>>n;
    for(int i = 1;i<n;i++){
        int a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1,0);
    reroot(1,0,0,1);
    cout<<overMA<<" "<<overCNT<<endl;
}

Compilation message (stderr)

road.cpp: In function 'void reroot(long long int, long long int, long long int, long long int)':
road.cpp:39:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |             for(int i = 3;i<v.size();i++)if(v[i].first==x)C+=v[i].second;
      |                           ~^~~~~~~~~
road.cpp:38:17: warning: unused variable 'A' [-Wunused-variable]
   38 |             int A = v[0].second , B = v[1].second , C = v[2].second;
      |                 ^
road.cpp:43:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             for(int i = 3;i<v.size();i++)if(v[i].first==x)C+=v[i].second;
      |                           ~^~~~~~~~~
road.cpp:49:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |             for(int i = 3;i<v.size();i++){
      |                           ~^~~~~~~~~
road.cpp:46:17: warning: unused variable 'A' [-Wunused-variable]
   46 |             int A = v[0].second , B = v[1].second , C = v[2].second;
      |                 ^
road.cpp:59:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |             for(int i = 3;i<v.size();i++){
      |                           ~^~~~~~~~~

• Subtask 1: 19 / 19
• Subtask 2: 33 / 33
• Subtask 3: 48 / 48