Submission #37802

#	Time	Username	Problem	Language	Result	Execution time	Memory
37802		mirbek01	Shymbulak (IZhO14_shymbulak)	C++14	50 / 100	949 ms	200872 KiB

shymbulak

# 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 (stderr)

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 / 30
• Subtask 2: 20 / 20
• Subtask 3: 0 / 50