oj.uz

Submission #342370

# Submission time Handle Problem Language Result Execution time Memory
342370 2021-01-02T01:42:42 Z cow Hard route (IZhO17_road) C++14
0 / 100
 10 ms 12140 KB 
#include <iostream>
#include <vector>
#define ll long long
using namespace std;
#define mn (ll) 5e5+5

ll N;
vector<ll> graph[mn];
ll mD[mn][3];
ll mLoc, mDist, root;
ll dist[mn];
ll pa[mn];

ll ans, ansNum = 1;
bool depthB;
bool rev;

void upd(ll l, ll v){
    if(v >= mD[l][0]){
        mD[l][2] = mD[l][1];
        mD[l][1] = mD[l][0];
        mD[l][0] = v;
    } else if (v >= mD[l][1]){
        mD[l][2] = mD[l][1];
        mD[l][1] = v;
    } else mD[l][2] = max(mD[l][2], v);
}

void passDown(ll l, ll p){
    for(ll j : graph[l]) if(j!=p){
        ll pass = mD[l][0];
        if(mD[j][0] == pass - 1) pass = mD[l][1];
        upd(j, pass+1);
        passDown(j,l);
    }
}

ll dfs(ll l, ll p){
    for(ll j: graph[l]) if(j!=p) {
        dist[j] = dist[l]+1;
        if(dist[j] > mDist){
            mDist = dist[j];
            mLoc = j;
        }
        ll depC = dfs(j, l);
        if(!depthB) continue;
        upd(l,depC);
    }
    if(!depthB) return 0;
    return mD[l][0]+1;
}

void check(ll H){
    if(H > ans) {ans = H; ansNum = 0;}
    if(H == ans) {ansNum++;}
}
void hard(ll l){
    if(graph[l].size() < 3){
        if(ans==0) ansNum = 1;
        return;
    }
    ll H = (mD[l][1] + mD[l][0])*mD[l][2]; check(H);
    H = mD[l][1] * (mD[l][0] + mD[l][2]); check(H);
    H = mD[l][0] * (mD[l][1] + mD[l][2]); check(H);
}
int main() {
    cin >> N;
    for(ll i = 0; i < N-1; i++){
        ll a, b; cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    dfs(1,-1); root = mLoc; dist[root] = 0; mDist = 0;
    depthB = true;
    dfs(root, -1);
    passDown(root, -1);
    for(ll i = 1; i <= N; i++){
       // cout << i << " " << mD[i][0] << " " << mD[i][1] << " " << mD[i][2] << " " << endl;
        hard(i);
    }
    cout << ans << " " << ansNum << endl;
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12140 KB Output is correct
2 Correct 8 ms 12140 KB Output is correct
3 Correct 9 ms 12140 KB Output is correct
4 Correct 9 ms 12140 KB Output is correct
5 Correct 10 ms 12140 KB Output is correct
6 Correct 9 ms 12140 KB Output is correct
7 Incorrect 10 ms 12140 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12140 KB Output is correct
2 Correct 8 ms 12140 KB Output is correct
3 Correct 9 ms 12140 KB Output is correct
4 Correct 9 ms 12140 KB Output is correct
5 Correct 10 ms 12140 KB Output is correct
6 Correct 9 ms 12140 KB Output is correct
7 Incorrect 10 ms 12140 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12140 KB Output is correct
2 Correct 8 ms 12140 KB Output is correct
3 Correct 9 ms 12140 KB Output is correct
4 Correct 9 ms 12140 KB Output is correct
5 Correct 10 ms 12140 KB Output is correct
6 Correct 9 ms 12140 KB Output is correct
7 Incorrect 10 ms 12140 KB Output isn't correct
8 Halted 0 ms 0 KB -