oj.uz

답안 #341503

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
341503 2020-12-29T21:27:02 Z nickmet2004 Hard route (IZhO17_road) C++11
0 / 100
 19 ms 31724 KB 
#include<bits/stdc++.h>
#define int long long
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 A= 0;
            for(int x = 0; x < D[u].size(); ++x) if(D[u][x] ==x1)A++;
            cnt += (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] == 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;
    }

}
 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

road.cpp: In function 'void solve()':
road.cpp:45:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             for(int x = 0; x < D[u].size(); ++x) if(D[u][x] ==x1)A++;
      |                            ~~^~~~~~~~~~~~~
road.cpp:50:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long 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: 'long long int' and 'std::vector<long long 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: 'long long int' and 'std::vector<long long 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++;
      |                       ~~^~~~~~~~~~~~~
road.cpp: At global scope:
road.cpp:64:8: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   64 |  main (){
      |        ^

Subtask #1
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 31724 KB Output is correct
2 Correct 19 ms 31724 KB Output is correct
3 Correct 19 ms 31724 KB Output is correct
4 Correct 19 ms 31724 KB Output is correct
5 Correct 19 ms 31724 KB Output is correct
6 Correct 19 ms 31724 KB Output is correct
7 Incorrect 19 ms 31724 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 31724 KB Output is correct
2 Correct 19 ms 31724 KB Output is correct
3 Correct 19 ms 31724 KB Output is correct
4 Correct 19 ms 31724 KB Output is correct
5 Correct 19 ms 31724 KB Output is correct
6 Correct 19 ms 31724 KB Output is correct
7 Incorrect 19 ms 31724 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 31724 KB Output is correct
2 Correct 19 ms 31724 KB Output is correct
3 Correct 19 ms 31724 KB Output is correct
4 Correct 19 ms 31724 KB Output is correct
5 Correct 19 ms 31724 KB Output is correct
6 Correct 19 ms 31724 KB Output is correct
7 Incorrect 19 ms 31724 KB Output isn't correct
8 Halted 0 ms 0 KB -