제출 #342291

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
342291		nickmet2004	Hard route (IZhO17_road)	C++11	0 / 100	15 ms	23808 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];
        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 WW = 1;
        if(x1 == x3){
            int A= 0;
            for(int x = 0; x < D[u].size(); ++x) if(D[u][x].F ==x1)A++,  WW *= D[u][x].S;
            cnt += (WW * A * (A - 1) * (A - 2)) / 2;
            continue;
        }
        if(x1 == x2){
            int A =0;
            for(int x = 0; x < D[u].size(); ++x) if(D[u][x].F == x3)A++ , WW *= D[u][x].S;
            cnt += A * WW; continue;
        }
        if(x2 == x3){
            int A= 0;
            for(int x = 0; x< D[u].size(); ++x)if(D[u][x].F == x2)A++, WW *= D[u][x].S;
            cnt += (WW * A * (A - 1)) / 2;continue;
        }
        int A = 0;
        for(int x = 0;x < D[u].size(); ++x)if(D[u][x].F == x3)A++ , WW *= D[u][x].S;
        cnt += A * WW;
    }
}

 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;

}

컴파일 시 표준 에러 (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)A++,  WW *= D[u][x].S;
      |                            ~~^~~~~~~~~~~~~
road.cpp:73: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]
   73 |             for(int x = 0; x < D[u].size(); ++x) if(D[u][x].F == x3)A++ , WW *= D[u][x].S;
      |                            ~~^~~~~~~~~~~~~
road.cpp:78: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]
   78 |             for(int x = 0; x< D[u].size(); ++x)if(D[u][x].F == x2)A++, WW *= D[u][x].S;
      |                            ~^~~~~~~~~~~~~
road.cpp:82: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]
   82 |         for(int x = 0;x < D[u].size(); ++x)if(D[u][x].F == x3)A++ , WW *= D[u][x].S;
      |                       ~~^~~~~~~~~~~~~
road.cpp: At global scope:
road.cpp:87:8: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   87 |  main (){
      |        ^

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