oj.uz

Submission #497694

# Submission time Handle Problem Language Result Execution time Memory
497694 2021-12-23T15:50:29 Z infertechno2 Shymbulak (IZhO14_shymbulak) C++17
50 / 100
 606 ms 196480 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,false);
    queue<ll> to_process;
    to_process.push(start_node);
    dist[start_node][start_node]={0,1};
    visited[start_node]=true;
    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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 412 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 0 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 0 ms 460 KB Output is correct
10 Correct 0 ms 460 KB Output is correct
11 Correct 0 ms 460 KB Output is correct
12 Correct 0 ms 460 KB Output is correct
13 Correct 1 ms 1228 KB Output is correct
14 Correct 6 ms 4428 KB Output is correct
15 Correct 5 ms 4428 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7008 KB Output is correct
2 Correct 10 ms 8728 KB Output is correct
3 Correct 20 ms 12328 KB Output is correct
4 Correct 22 ms 12236 KB Output is correct
5 Correct 487 ms 188556 KB Output is correct
6 Correct 391 ms 196368 KB Output is correct
7 Correct 606 ms 196388 KB Output is correct
8 Correct 476 ms 196480 KB Output is correct
9 Correct 511 ms 196336 KB Output is correct
10 Correct 526 ms 194740 KB Output is correct

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 -