oj.uz

Submission #37802

# Submission time Handle Problem Language Result Execution time Memory
37802 2017-12-28T06:40:18 Z mirbek01 Shymbulak (IZhO14_shymbulak) C++14
50 / 100
 949 ms 200872 KB 
# include <bits/stdc++.h>

# define pb push_back
# define fr first
# define sc second
# define mk make_pair

using namespace std;

const int inf = 1e9 + 7;
const int N = 5e3 + 5;

typedef long long ll;

int n, m, ans, mx, dist[N][N], cnt[N][N];
vector <int> g[N];

void bfs(int x)
{
      queue <int> q;
      q.push(x);
      cnt[x][x] = 1;
//      cout << x << endl;
      while(!q.empty())
      {
            int v = q.front();
            q.pop();

            for(int i = 0; i < g[v].size(); i ++)
            {
                  int to = g[v][i];
                  if(dist[x][to] == dist[x][v] + 1 || dist[x][to] == 0)
                        cnt[x][to] += cnt[x][v];
                  if(!dist[x][to] && to != x)
                  {
                        dist[x][to] = dist[x][v] + 1;
                        q.push(to);
                  }
            }
      }
//      for(int i = 1; i <= n; i ++)
//            cout << dist[x][i] << " ";
//      cout << endl;
//      for(int i = 1; i <= n; i ++)
//            cout << cnt[x][i] << " ";
//      cout << endl;
}

int main()
{
      cin >> n;

      for(int i = 1; i <= n; i ++)
      {
            int x, y;
            cin >> x >> y;
            g[x].pb(y);
            g[y].pb(x);
      }

      for(int i = 1; i <= n; i ++)
            bfs(i);

      for(int i = 1; i <= n; i ++)
            for(int j = i + 1; j <= n; j ++)
                  mx = max(mx, dist[i][j]);

//      for(int i = 1; i <= n; i ++)
//      {
//            for(int j = i + 1; j <= n; j ++)
//            {
//                  cout << i << " " << j << " " << dist[i][j] << " " << cnt[i][j] << endl;
//            }
//      }

      for(int i = 1; i <= n; i ++)
            for(int j = i + 1; j <= n; j ++)
                  if(mx == dist[i][j]) ans += cnt[i][j];

      cout << ans << endl;
}

Compilation message

shymbulak.cpp: In function 'void bfs(int)':
shymbulak.cpp:29:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < g[v].size(); i ++)
                              ^

Subtask #1
30.0 / 30.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 197836 KB Output is correct
2 Correct 13 ms 197836 KB Output is correct
3 Correct 16 ms 197836 KB Output is correct
4 Correct 33 ms 197836 KB Output is correct
5 Correct 779 ms 197968 KB Output is correct
6 Correct 463 ms 198100 KB Output is correct
7 Correct 896 ms 197968 KB Output is correct
8 Correct 949 ms 197968 KB Output is correct
9 Correct 856 ms 197968 KB Output is correct
10 Correct 886 ms 197968 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 126 ms 200872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -