oj.uz

Submission #497692

# Submission time Handle Problem Language Result Execution time Memory
497692 2021-12-23T15:43:53 Z infertechno2 Shymbulak (IZhO14_shymbulak) C++17
30 / 100
 425 ms 262148 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

void bfs(ll start_node){
    vector<ll> 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();
        visited[curr_node]=2;
        to_process.pop();
        for(auto itr:adj[curr_node]){
            if(visited[itr]==0){
                dist[start_node][itr]=dist[start_node][curr_node];
                dist[start_node][itr].first++;
                visited[itr]=1;
                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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 452 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 432 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 452 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 0 ms 460 KB Output is correct
12 Correct 1 ms 420 KB Output is correct
13 Correct 1 ms 1456 KB Output is correct
14 Correct 10 ms 6448 KB Output is correct
15 Correct 7 ms 6412 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 10928 KB Output is correct
2 Correct 13 ms 13820 KB Output is correct
3 Correct 23 ms 20292 KB Output is correct
4 Correct 25 ms 20276 KB Output is correct
5 Runtime error 425 ms 262148 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

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