oj.uz

Submission #90861

# Submission time Handle Problem Language Result Execution time Memory
90861 2018-12-25T03:15:08 Z daniel_02 Shymbulak (IZhO14_shymbulak) C++17
50 / 100
 1500 ms 11476 KB 
#include <bits/stdc++.h>

#define fr first
#define pb push_back
#define sc second
#define ll long long

using namespace std;

const int N = 2e5 + 7;
const int inf = 1e6 + 7;

vector<int>g[N];
int d[N];
int cn[N];
queue<pair<int, int>>q;
void mems(){
	for (int i = 0; i < N; i++)
		d[i] = inf;
	queue<pair<int, int>>empty;
	swap(q, empty);
}
void dance(int a)
{
	mems();
	q.push({a, 0});
	d[a] = 0;
	while (!q.empty())
	{
		int v = q.front().fr, cs = q.front().sc;
		q.pop();
		
		if (cs > d[v])continue;
		
		for (int i = 0; i < g[v].size(); i++)
		{
			int to = g[v][i];
			if (cs + 1 <= d[to])
			{
				d[to] = cs + 1;
				cn[d[to]]++;
				q.push({to, d[to]});
			}
		}
	}
}

main()
{
	int n;
	
	cin >> n;
	
	for (int i = 1; i <= n; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		g[a].pb(b);
		g[b].pb(a);
	}
	int mx = 0;
	for (int i = 1; i <= n; i++)
	{
		dance(i);
		for (int j = 1; j <= n; j++)
		{
			if (i == j)continue;
			mx = max(mx, d[j]);
		}
	}
	cout << cn[mx] / 2 << endl;
}

Compilation message

shymbulak.cpp: In function 'void dance(int)':
shymbulak.cpp:35:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < g[v].size(); i++)
                   ~~^~~~~~~~~~~~~
shymbulak.cpp: At global scope:
shymbulak.cpp:48:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6008 KB Output is correct
2 Correct 7 ms 6120 KB Output is correct
3 Correct 7 ms 6120 KB Output is correct
4 Correct 7 ms 6120 KB Output is correct
5 Correct 8 ms 6260 KB Output is correct
6 Correct 8 ms 6260 KB Output is correct
7 Correct 8 ms 6268 KB Output is correct
8 Correct 9 ms 6268 KB Output is correct
9 Correct 8 ms 6268 KB Output is correct
10 Correct 8 ms 6268 KB Output is correct
11 Correct 8 ms 6268 KB Output is correct
12 Correct 7 ms 6268 KB Output is correct
13 Correct 21 ms 6268 KB Output is correct
14 Correct 56 ms 6268 KB Output is correct
15 Correct 55 ms 6268 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 6428 KB Output is correct
2 Correct 86 ms 6428 KB Output is correct
3 Correct 111 ms 6436 KB Output is correct
4 Correct 117 ms 6436 KB Output is correct
5 Correct 950 ms 6888 KB Output is correct
6 Correct 873 ms 6888 KB Output is correct
7 Correct 1029 ms 6916 KB Output is correct
8 Correct 1097 ms 6964 KB Output is correct
9 Correct 973 ms 6964 KB Output is correct
10 Correct 1112 ms 6968 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1569 ms 11476 KB Time limit exceeded
2 Halted 0 ms 0 KB -