oj.uz

Submission #935331

# Submission time Handle Problem Language Result Execution time Memory
935331 2024-02-29T03:42:47 Z Darren0724 Hard route (IZhO17_road) C++17
0 / 100
 2 ms 608 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define all(x) x.begin(), x.end()
const int N=5005;
const int INF=1e9;
const int mod=1e9+9;
int n,ans=0,cnt=0;
vector<int> adj[N];
vector<int> deep(N),deg(N);
vector<int> dp1(N),dp2(N);
void upd(int i,int k){
    if(dp1[i]<k){
        dp2[i]=dp1[i];
        dp1[i]=k;
    }
    else if(dp2[i]<k){
        dp2[i]=k;
    }
}
void updans(int k,int cnt1){
    if(ans==k){
        cnt+=cnt1;
    }
    else if(k>ans){
        ans=k;
        cnt=cnt1;
    }
}
void dfs(int k,int pa) {
    for(int j:adj[k]){
        if(j==pa)continue;
        deep[j]=deep[k]+1;
        dfs(j,k);
        upd(k,dp1[j]);
    }
    updans(dp2[k]*(dp1[k]-deep[k]),1);
    if(dp1[k]==dp2[k])updans(dp2[k]*(dp1[k]-deep[k]),1);
    if(deg[k]==1)upd(k,deep[k]);
}
// deep[j]*deep[j1]
int32_t main() {
    LCBorz;
    cin>>n;
    for(int i=1;i<n;i++){
        int a,b;cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        deg[a]++,deg[b]++;
    }
    for(int i=1;i<=n;i++){
        if(deg[i]==1){
            dp1.assign(N,-INF);
            dp2.assign(N,0);
            deep.assign(N,0);
            dfs(i,i);
        }
    }    
    cout<<ans<<' '<<cnt/2<<endl;

    return 0;
}

Subtask #1
0 / 19.0

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

Subtask #2
0 / 33.0

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

Subtask #3
0 / 48.0

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