oj.uz

Submission #342337

# Submission time Handle Problem Language Result Execution time Memory
342337 2021-01-01T22:49:45 Z cow Hard route (IZhO17_road) C++14
0 / 100
 10 ms 12276 KB 
//
//  main.cpp
//  Hard Paths
//
//  Created by Isaac Noel on 1/1/21.
//

#include <iostream>
#include <vector>
using namespace std;
#define mn (int) 5e5+5

int N;
vector<int> graph[mn];
int mD[mn][2];
int mLoc, mDist, root;
int dist[mn];
int pa[mn];
int ans, ansNum;
bool depthB;

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

int dop=1, dPath;

void check(int H){
    if(H > ans) {ans = H; ansNum = 0;}
    if(H == ans) {ansNum++;}
}
void retrace(int loc){
    if(dop == dPath) return;
    if(graph[loc].size() < 3){
        if(ans == 0) ansNum = 1;
        dop++; retrace(pa[loc]);
        return;
    }
    int dist = mD[loc][0];
    if(dist == dop) dist = mD[loc][1];
    int H = dPath * dist; check(H);
    H = (dop+dist) * (dPath-dop); check(H);
    H = (dist + dPath-dop) * dop; check(H);
    dop++;
    retrace(pa[loc]);
}
int main() {
    cin >> N;
    for(int i = 0; i < N-1; i++){
        int 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;
    dPath = dfs(root, -1)-1;
    retrace(pa[mLoc]);
    cout << ans << " " << ansNum;
}

Subtask #1
0 / 19.0

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

Subtask #2
0 / 33.0

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

Subtask #3
0 / 48.0

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