Submission #341487

#	Time	Username	Problem	Language	Result	Execution time	Memory
341487		nickmet2004	Hard route (IZhO17_road)	C++11	0 / 100	18 ms	27756 KiB

road

#include<bits/stdc++.h>

using namespace std;
const int N = 5e5 + 5;
int n;
vector<int> adj[N],  D[N];
int d[N],  d1[N] , d2[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);
        d[u] = max(d[u] , d[v] + 1);
        if(d2[u] < d[v] + 1) d2[u] = d[v] + 1;
        if(d2[u] > d1[u]) swap(d1[u] , d2[u]);
    }
    for(int v : adj[u]) if(v != p)D[u].emplace_back(d[v]+1);
}
void dfsU(int u = 1, int p = 0){
    for(int v : adj[u]){
        if(v==p)continue;
        dpU[v] = dpU[u] + 1;
        if(d[v] + 1 == d1[u]){
            if(d2[u] != -1) dpU[v] = max(dpU[v], d2[u] + 1);
        } else dpU[v] = max(dpU[v] , d1[u] + 1);
        dfsU(v , u);
    }
}
void solve(){
    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] , x2 = D[u][1] , x3 = D[u][2];
       // 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] , x2 = D[u][1] , x3 = D[u][2];
        if(mx != x1 * (x2 + x3)) continue;
        if(x1 == x2 && x2 == x3){
            int x = 0;
            for(x = 0; x < D[u].size(); ++x) if(D[u][x] != x1)break;
            cnt += (x * (x - 1)) / 2; continue;
        }
        if(x1 == x2){
            int A =0;
            for(int x = 0; x < D[u].size(); ++x) if(D[u][x] == x3)A++;
            cnt += A; continue;
        }
        if(x2 == x3){
            int A= 0;
            for(int x = 0; x< D[u].size(); ++x)if(D[u][x] == x2)A++;
            cnt += (A * (A - 1)) / 2;continue;
        }
        int A = 0;
        for(int x = 0;x < D[u].size(); ++x)if(D[u][x] == x3)A++;
        cnt += A;
    }

}
int 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);
    }
    memset(d1, -1 , sizeof(d1)); memset(d2 , -1, sizeof(d2));
    dfsD();
    //for(int i = 1; i <= n; ++i)cout << d1[i] << " " << d2[i] << endl;
    /*
    for(int i = 1; i <= n; ++i){
        cout << i << ":: i  ";
        for(int x : D[i])cout << x << " ";cout << endl;
    }
    */
    dfsU();
    for(int i = 1; i <= n; ++i)if(dpU[i])D[i].emplace_back(dpU[i]);
    solve();
    if(!cnt)cnt = 1;
    cout << mx << " " << cnt;
    //cout << endl;
    //for(int i = 1; i <= n; ++i)cout << dpU[i] << " ";
}

Compilation message (stderr)

road.cpp: In function 'void solve()':
road.cpp:45:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             for(x = 0; x < D[u].size(); ++x) if(D[u][x] != x1)break;
      |                        ~~^~~~~~~~~~~~~
road.cpp:50:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             for(int x = 0; x < D[u].size(); ++x) if(D[u][x] == x3)A++;
      |                            ~~^~~~~~~~~~~~~
road.cpp:55:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |             for(int x = 0; x< D[u].size(); ++x)if(D[u][x] == x2)A++;
      |                            ~^~~~~~~~~~~~~
road.cpp:59:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for(int x = 0;x < D[u].size(); ++x)if(D[u][x] == x3)A++;
      |                       ~~^~~~~~~~~~~~~

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