oj.uz

Submission #497693

# Submission time Handle Problem Language Result Execution time Memory
497693 2021-12-23T15:45:18 Z infertechno2 Shymbulak (IZhO14_shymbulak) C++17
0 / 100
 13 ms 8652 KB 
#include <bits/stdc++.h>

using namespace std;

typedef int ll;

const ll Size=5e3+2;
vector<ll> adj[Size];
pair<ll,ll> dist[Size][Size];

void bfs(ll start_node){
    vector<bool> visited(Size,0);
    queue<ll> to_process;
    to_process.push(start_node);
    dist[start_node][start_node]={0,1};
    while(!to_process.empty()){
        ll curr_node=to_process.front();
        to_process.pop();
        for(auto itr:adj[curr_node]){
            if(visited[itr]==false){
                dist[start_node][itr]=dist[start_node][curr_node];
                dist[start_node][itr].first++;
                visited[itr]=true;
                to_process.push(itr);
                continue;
            }
            if(dist[start_node][itr].first>dist[start_node][curr_node].first){
                dist[start_node][itr].second+=dist[start_node][curr_node].second;
            }
        }
    }
}


void solve(){
    ll n;
    pair<ll,ll> ans={0,0};
    cin>>n;
    for(ll i=0;i<n;i++){
        ll from,to;
        cin>>from>>to;
        adj[from].push_back(to);
        adj[to].push_back(from);
    }
    for(ll i=1;i<=n;i++){
        bfs(i);
        for(ll j=1;j<=n;j++){
            if(dist[i][j].first>ans.first){
                ans=dist[i][j];
            }else{
                if(dist[i][j].first==ans.first){
                    ans.second+=dist[i][j].second;
                }
            }
        }
    }
    cout<<ans.second/2<<endl;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t=1;
    while(t--){
        solve();
    }
    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 7016 KB Output is correct
2 Incorrect 10 ms 8652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 716 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -