Submission #342753

#	Time	Username	Problem	Language	Result	Execution time	Memory
342753		nickmet2004	Hard route (IZhO17_road)	C++11	100 / 100	933 ms	145012 KiB

road

#include<bits/stdc++.h>
#define F first
#define S second
#define int long long
using namespace std;
typedef pair<int , int> ipair;
const int N = 5e5 + 5;
int n;
vector<int> adj[N];
vector<ipair> D[N];
ipair dpD[N] , dpU[N];
int mx , cnt;
void dfsD(int u = 1 , int p = 0){
    for(int v : adj[u]){
        if(v==p)continue;
        dfsD(v , u);
        if(dpD[v].F + 1 > dpD[u].F) dpD[u] = dpD[v] , dpD[u].F++;
        else if(dpD[v].F + 1 == dpD[u].F) dpD[u].S += dpD[v].S;
    }
    if(adj[u].size() == 1 && u != 1) dpD[u].S = 1;
    for(int v : adj[u]) if(v != p)D[u].emplace_back(dpD[v].F + 1, dpD[v].S);
}
void dfsU(int u = 1, int p = 0){
    pair<int , int > d1 , d2;
    d1.F = d1.S = d2.F= d2.S = 0;
    d1 = dpD[u];
    ///d1.F--;
    //cout << d1.F << " " << d1.S << " kaaa " << endl;
    for(int v : adj[u]){
        if(v==p || d1.F == dpD[v].F + 1)continue;
        if(d2.F < dpD[v].F + 1)d2 = dpD[v] , d2.F++;
        else if(d2.F == dpD[v].F + 1) d2.S += dpD[v].S;
    }
    //cout << d2.F << " " << d2.S << " uaaaa "<< endl;
    if(u == 1) dpU[u].S = 1;
    for(int v : adj[u]){
        if(v==p)continue;
        if(d1.F == dpD[v].F + 1 && d1.S == dpD[v].S) dpU[v] = d2;
        else if(d1.F == dpD[v].F + 1 && d1.S > dpD[v].S) dpU[v].F = d1.F , dpU[v].S = d1.S - dpD[v].S;
        else dpU[v] = d1;
        if(dpU[v].F < dpU[u].F) dpU[v] = dpU[u];
        else if(dpU[v].F == dpU[u].F) dpU[v].S += dpU[u].S;
        dpU[v].F++;
        dfsU(v , u);
    }
}


void solve(){
    //cout << "HOO" << endl;
    for(int u = 1; u <= n; ++u){
        if(D[u].size() < 3) continue;
        sort(D[u].rbegin() , D[u].rend());
        int x1 = D[u][0].F , x2 = D[u][1].F , x3 = D[u][2].F;
        //cout << x1 << " " << x2 << " " << x3 << endl;
        mx = max(mx , x1 * (x2 + x3));
    }
    //cout << mx << " mx "<<endl;

    for(int u = 1; u <= n; ++u){
        if(D[u].size() < 3)continue;
        int x1 = D[u][0].F , x2 = D[u][1].F , x3 = D[u][2].F;
        if(mx != x1 * (x2 + x3)) continue;
        ///
        int Y = 0;
        if(x1 == x3){
            for(int x = 0; x < D[u].size(); ++x) if(D[u][x].F ==x1)Y += D[u][x].S;
            for(int x = 0; x < D[u].size(); ++x){
                if(D[u][x].F == x1) cnt += (Y - D[u][x].S) * D[u][x].S , Y -= D[u][x].S;
            }
            continue;
        }
        ///
        if(x1 == x2){
            for(int x = 0; x < D[u].size(); ++x) if(D[u][x].F == x3)Y += D[u][x].S;
            cnt += (D[u][0].S + D[u][1].S) * Y;
            continue;
        }
        if(x2 == x3){
            for(int x = 0; x< D[u].size(); ++x)if(D[u][x].F == x2) Y += D[u][x].S;
            for(int x= 0; x < D[u].size(); ++x){
                if(D[u][x].F == x2) cnt += D[u][x].S * (Y - D[u][x].S), Y-= D[u][x].S;
            }
            continue;
        }
        for(int x = 0;x < D[u].size(); ++x)if(D[u][x].F == x3)Y+= D[u][x].S;
        cnt += D[u][1].S * Y;
    }
}

 main (){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int i = 1; i < n; ++i){
        int u , v; cin >> u >> v;
        adj[u].emplace_back(v); adj[v].emplace_back(u);
    }
    dfsD();
    //for(int i = 1; i <= n; ++i)cout << dpD[i].F << " "; cout << endl;

    dfsU();
    for(int i = 1; i <= n; ++i)if(dpU[i].F)D[i].emplace_back(dpU[i]);
    //for(int i= 1; i <= n; ++i)cout << dpU[i].F << " "; cout << endl;
    solve();
    if(!cnt)cnt = 1;
    cout << mx << " " << cnt;

}

Compilation message (stderr)

road.cpp: In function 'void solve()':
road.cpp:67:30: 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]
   67 |             for(int x = 0; x < D[u].size(); ++x) if(D[u][x].F ==x1)Y += D[u][x].S;
      |                            ~~^~~~~~~~~~~~~
road.cpp:68:30: 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]
   68 |             for(int x = 0; x < D[u].size(); ++x){
      |                            ~~^~~~~~~~~~~~~
road.cpp:75:30: 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]
   75 |             for(int x = 0; x < D[u].size(); ++x) if(D[u][x].F == x3)Y += D[u][x].S;
      |                            ~~^~~~~~~~~~~~~
road.cpp:80:29: 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]
   80 |             for(int x = 0; x< D[u].size(); ++x)if(D[u][x].F == x2) Y += D[u][x].S;
      |                            ~^~~~~~~~~~~~~
road.cpp:81:29: 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]
   81 |             for(int x= 0; x < D[u].size(); ++x){
      |                           ~~^~~~~~~~~~~~~
road.cpp:86:25: 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]
   86 |         for(int x = 0;x < D[u].size(); ++x)if(D[u][x].F == x3)Y+= D[u][x].S;
      |                       ~~^~~~~~~~~~~~~
road.cpp: At global scope:
road.cpp:91:8: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   91 |  main (){
      |        ^

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